矩阵填数

我们下标从 1 开始。 三个例子分别运行，先看填数顺序，再跟着坐标走。

蛇形填数（难）

2045：【例5.13】蛇形填数

从右上角开始，按下、左、上、右填数，碰到边界或已填位置就转向。1 <= n <= 20。

第一种写法，四个方向分别处理

#include <iostream>

using namespace std;

int a[25][25], n;
int idx;

int main() {
    cin >> n;

    int i = 1, j = n;
    while (idx < n * n) {
        while (i <= n && !a[i][j]) {
            a[i][j] = ++idx;
            i++;
        }
        i--, j--;

        while (j >= 1 && !a[i][j]) {
            a[i][j] = ++idx;
            j--;
        }
        j++, i--;

        while (i >= 1 && !a[i][j]) {
            a[i][j] = ++idx;
            i--;
        }
        i++, j++;

        while (j <= n && !a[i][j]) {
            a[i][j] = ++idx;
            j++;
        }
        i++, j--;
    }

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++) {
            cout << a[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

每个方向走完，先退一步，再朝下一方向走一步。

第二种写法，使用方向数组

dx 记录行的变化，dy 记录列的变化，顺序是下、左、上、右。

// 第二种写法，方向数组
#include <iostream>

using namespace std;

int a[25][25];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};

int main() {
    int n;
    cin >> n;
    int x = 1, y = n, d = 0;
    for (int idx = 1; idx <= n * n; idx++) {
        a[x][y] = idx;
        if (idx == n * n) {
            break; // 已填完，不再找下一个位置
        }
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 1 || nx > n || ny < 1 || ny > n || a[nx][ny] != 0) {
            d = (d + 1) % 4;
            nx = x + dx[d];
            ny = y + dy[d];
        }
        x = nx;
        y = ny;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << a[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

d 是方向编号，(d + 1) % 4 切换到下一方向。

先判断边界，再访问数组，条件顺序别换。

两种写法都试试 n = 1，应填入 1。

先确定起点、方向、转向条件。 画个小例子，跟着代码走。

斜行方阵（难）

3368：练63.2 斜行方阵

枚举斜线起点，沿右下方填数。1 <= n <= 20。

起点先沿第一行从右往左，再沿第一列从第二行往下，左上角不重复。

#include <iostream>
#include <cstdio>

using namespace std;

int a[25][25];

int main() {
    int n;
    cin >> n;
    int idx = 1;
    for (int k = n; k >= 1; k--) {
        int x = 1, y = k;
        while (x <= n && y <= n) {
            a[x][y] = idx++;
            x++;
            y++;
        }
    }
    for (int k = 2; k <= n; k++) {
        int x = k, y = 1;
        while (x <= n && y <= n) {
            a[x][y] = idx++;
            x++;
            y++;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%4d", a[i][j]);
        }
        cout << '\n';
    }

    return 0;
}

行号、列号同时加 1，就沿右下方走一步。

神奇的幻方（难）

22：神奇的幻方

幻方每行、每列、两条对角线的数字之和都相同。

输入 n，构造 (2n-1) × (2n-1) 的幻方。 1 <= n <= 20。

从第一行中间开始，依次往右上方填；越界就绕到另一边，右上角或右上方已填时改向下填。

#include <iostream>

using namespace std;

int a[50][50], n;

int main() {
    cin >> n;

    int x = 1, y = n, idx = 1; // 输入的n，正好是扩展后第一行的中间列
    n = 2 * n - 1;
    while (idx <= n * n) {
        a[x][y] = idx++;

        if (x == 1) {
            if (y == n) x++;
            else x = n, y++;
        }
        else if (y == n) y = 1, x--;
        else if (a[x - 1][y + 1]) x++;
        else x--, y++;
    }

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++) {
            cout << a[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

先处理边界，再检查右上方是否已填。