- 本篇仅提供一个解题思路:使用 756. 蛇形矩阵 内类似的蛇形填数法
【具体来说】:
记录一下向 ↑ → ↓ ←
四个方向(顺时针)的偏移量
dx[] = {-1,0,1,0};
如 dx[1] = 0和 dy[1] = 1就表示向右边走一步的坐标偏移(行不变,列+1)
dy[] = {0,1,0,-1};
这类方法还可以表示当前点的各种方向的便宜,比如棋子的落位
撞墙的时候改一下方向。【撞墙包括 出界
和 遇到已经填好的格子
】
- 用数组记录一下各个方向的偏移量是非常高效的写代码技巧,避免写一堆if判断,导致代码非常冗长难看
C++ 代码
#include <iostream>
using namespace std;
const int N = 110;
int n;
int g[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
void fill() {
int x = 0, y = 0; //从[0,0]开始填
int num = 1, direction = 1; //第一圈填数字1,先向右走
for (int i = 0; i < n * n; i++) {
g[x][y] = num; //填数
int a = x + dx[direction],
b = y + dy[direction]; //用变量a,b试探下一步是否撞墙
if (!(a >= 0 && a < n && b >= 0 && b < n && g[a][b] == 0)) { //撞墙
direction = (direction + 1) % 4; //顺时针改变一次方向
if (direction == 1) //如果又回到了向右走,所填数字+1
num++;
}
x += dx[direction], y += dy[direction]; //改变当前坐标
}
//输出答案,顺便将g数组初始化
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << g[i][j] << ' ';
g[i][j] = 0;
}
cout << endl;
}
cout << endl;
}
int main() {
while (cin >> n, n) {
fill();
}
return 0;
}