-
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;
}
-
螺旋方阵：
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;
}
-
蛇形方阵（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;
}
网友评论