|
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
一、题目描述
Description
给出一个不大于 9 的正整数 n，输出 n×n 的蛇形方阵。
从左上角填上 1 开始，顺时针方向依次填入数字。
如同样例所示。注意每个数字有都会占用 3 个字符，前面使用空格补齐。
?
输入格式
一个整数n。
输出格式
n对应的蛇形方阵。 ?
输入样例
4
?
输出样例
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7 ?
提示
注意输出格式！
二、题解
因为数据量不大，因此直接用递归来写，思路清晰，先设置dx,dy来标记方向，再根据边界来改变方向。
#include<iostream>
#include<cstdio>
using namespace std;
int dx = 0, dy = 1;
int v[10][10], a[10][10];
int n;
void dfs(int value,int x,int y) {
v[x][y] = 1;
a[x][y] = value;
if (value == n * n)
return;
else{
int nx = x + dx;
int ny = y + dy;
if (nx >= 0 && nx < n && ny >= 0 && ny < n && !v[nx][ny] && !a[nx][ny]) {
dfs(value + 1, nx, ny);
}
else if (v[nx][ny] && dy == 1 || ny >= n) {
dx = 1;
dy = 0;
dfs(value + 1, x + 1, y);
}
else if (nx >= n || v[nx][ny]&& dx == 1) {
dx = 0;
dy = -1;
dfs(value + 1, x, y - 1);
}
else if (ny < 0 || v[nx][ny] && dy == -1) {
dx = -1;
dy = 0;
dfs(value + 1, x - 1, y);
}
else{
dx = 0;
dy = 1;
dfs(value + 1, x, y + 1);
}
}
}
int main(void) {
cin >> n;
dfs(1, 0, 0);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
printf("%3d", a[i][j]);
printf("\n");
}
return 0;
}
|