03 各种简单数字方阵

1. n阶奇数幻方： image.png
   

   类似于这样一种n×n的矩阵，共有数字1 -- n * n，矩阵大小是n * n。
   矩阵特点是每行之和，每列之和，以及两条主辅对角线上的数字之和完全相等。（注意n为奇数）

n阶奇数幻方的生成特点：从第一行中间开始（初始为1），一直向右上角“走”，如果超过了边界，则跳转到边界对面（i方向跳转到最底边n，j方向跳转到最左边1）。

如此模拟即可：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;

int nums[22][22];

void print(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%5d", nums[i][j]);
        }
        printf("\n");
    }
}

bool is_valid(int x, int n) {
    return 1 <= x && x <= n;
}

void solve(int n) {
    int i = 1, j = n / 2 + 1, cnt = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            nums[i][j] = -1;
        }
    }
    nums[i][j] = cnt++;
    while (cnt <= n * n) {
        i -= 1;
        j += 1;
        if (nums[i][j] == 0) {
            if (! is_valid(i, n) && ! is_valid(j, n)) {
                i++;
                j--;
                i++;
            }
            else if (is_valid(i, n)) {
                j = 1;
            }
            else if (is_valid(j, n)) {
                i = n;
            }
        }
        else if (nums[i][j] != -1) {
            i++;
            j--;
            i++;
        }
        nums[i][j] = cnt++;
    }
    print(n);
}

int main(int argc, char const *argv[])
{
    int n;
    scanf("%d", &n);
    solve(n);

    return 0;
}

2. 螺旋方阵： image.png
   

   特点是从左上角开始按照向右，向下，向左，向上的顺序循环往复。
   我们可以使用一个dirs二维数组来模拟每次可能走的方向。（注意如果改变螺旋方阵的螺旋方向，源码仅仅需要更改dirs方向数组的元素顺序即可）

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;

int nums[22][22];
int dirs[][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

void print(int n) {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            printf("%5d", nums[i][j]);
        }
        printf("\n");
    }
}

void solve(int n) {
    int cnt = 1, i = 1, j = 0, dir = 0, next_i, next_j;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            nums[i][j] = -1;
        }
    }
    while(cnt <= n * n) {
        next_i = dirs[dir][0] + i;
        next_j = dirs[dir][1] + j;
        i = next_i;
        j = next_j;
        if(nums[i][j] == -1) {
            nums[i][j] = cnt++;
        }
        else {
            i -= dirs[dir][0];
            j -= dirs[dir][1];
            dir++;
            if(dir == 4) dir = 0;
        }
    }
    print(n);
}

int main(int argc, char const *argv[])
{
    int n;
    scanf("%d", &n);
    solve(n);

    return 0;
}

3. 蛇形方阵（Z字型扫描）： image.png
   

   同螺旋方阵差不多，特点是从左上角开始，前半段按照向右，左下，下，右上的顺序；后半段按照下，左下，右，右上的顺序进行模拟移动。
   我们可以使用一个dirs二维数组来模拟每次可能走的方向。（注意如果改变蛇形方阵的行走方向，源码仅仅需要更改dirs方向数组的元素顺序即可）

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;

int nums[22][22];
int dirs[][2] = {{0, 1}, {1, -1}, {1, 0}, { -1, 1}};
int dirs_2[][2] = {{1, 0}, {1, -1}, {0, 1}, { -1, 1}};

void print(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%5d", nums[i][j]);
        }
        printf("\n");
    }
}

void solve(int n) {
    int dir = 0, cnt = 1, i = 1, j = 1, next_i, next_j;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            nums[i][j] = -1;
        }
    }
    nums[i][j] = cnt++;
    while (cnt <= n * n) {
        // 在一半以内
        if (i + j < n + 1) {
            next_i = i + dirs[dir][0];
            next_j = j + dirs[dir][1];
        }
        else {
            next_i = i + dirs_2[dir][0];
            next_j = j + dirs_2[dir][1];
        }
        i = next_i;
        j = next_j;
        if (nums[i][j] == 0) {
            i -= dirs[dir][0];
            j -= dirs[dir][1];
            dir++;
            if (dir == 4) dir = 0;
        }
        else {
            nums[i][j] = cnt++;
            if (dir != 1 && dir != 3) {
                dir++;
            }
        }
    }
    print(n);

}

int main(int argc, char const *argv[])
{
    int n;
    scanf("%d", &n);
    solve(n);

    return 0;
}

另一种蛇形方阵：

image.png

原理一样，只需要改变dirs数组的元素即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;

int nums[22][22];
int dirs[][2] = {{0, -1}, {1, 1}, {1, 0}, { -1, -1}};
int dirs_2[][2] = {{1, 0}, {1, 1}, {0, -1}, { -1, -1}};

void print(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%5d", nums[i][j]);
        }
        printf("\n");
    }
}

void solve(int n) {
    int dir = 0, cnt = 1, i = 1, j = n, next_i, next_j;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            nums[i][j] = -1;
        }
    }
    nums[i][j] = cnt++;
    while (cnt <= n * n) {
        // 在一半以内
        if (i < j) {
            next_i = i + dirs[dir][0];
            next_j = j + dirs[dir][1];
        }
        else {
            next_i = i + dirs_2[dir][0];
            next_j = j + dirs_2[dir][1];
        }
        i = next_i;
        j = next_j;
        if (nums[i][j] == 0) {
            i -= dirs[dir][0];
            j -= dirs[dir][1];
            dir++;
            if (dir == 4) dir = 0;
        }
        else {
            nums[i][j] = cnt++;
            if (dir != 1 && dir != 3) {
                dir++;
            }
        }
    }
    print(n);

}

int main(int argc, char const *argv[])
{
    int n;
    scanf("%d", &n);
    solve(n);

    return 0;
}