title: 蛇形矩阵
date: 2023-07-18 08:41:17
tags:
- c/c++
categories:
- 算法
- 笔试
top:
蛇形矩阵
题目来之acwing
题目（点击跳转）
输入两个整数 n 和 m，输出一个 n 行 m 列的矩阵，将数字1到 n×m 按照回字蛇形填充至矩阵中。
具体矩阵形式可参考样例。
输入格式
输入共一行，包含两个整数 n 和 m。
输出格式
输出满足要求的矩阵。
矩阵占 n 行，每行包含 m 个空格隔开的整数。
数据范围
1≤n,m≤100
输入样例：
3 3
输出样例：
1 2 3
8 9 4
7 6 5
思路：
这个题目是一个模拟填数的题目，将数字从1开始依次按照回字规则填入n*m的矩阵中，解题的思路是模拟数字的方向，当一个方向走不通时按照顺时针旋转一下方向，这样就可以接着走了，填完之后将数组打印即可。
这边使用一个偏移量来控制方向（x轴的正方向是向下，y轴的正方形是向右）
- 最开始肯定是从（0，0）开始y轴正方向走的，这时偏移量为
(0,1) - 当向右走出界或者碰到已经填过的位置时，这时需要顺时针旋转方向，也就是向下即x轴的正方向走，这时偏移量为
(1,0) - 当向下走出界或者碰到已经填过的位置时，这时需要顺时针旋转方向，也就是向左即y轴的负方向走，这时偏移量为
(0,-1) - 当向左走出界或者碰到已经填过的位置时，这时需要顺时针旋转方向，也就是向上即x轴的负方向走，这时偏移量为
(-1,0) - 当向上走出界或者碰到已经填过的位置时，这时需要顺时针旋转方向，也就是向右即y轴的正方向走，这是偏移量为
(0,1)
可以发现，当方向旋转四次后，就会有一次循环，这是可以定义两个数组维护这个偏移量，即dx和dy。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int res[N][N];
int main() {
cin >> n >> m;
// 定义四个方向的偏移量，向右即为(dx[0],dy[0])
int dx[]={0,1,0,-1}, dy[]={1,0,-1,0};
for(int x = 0, y = 0, k = 1, d = 0; k <= n*m; k ++) {
res[x][y] = k;
// 计算下一个位置的坐标
int a = x + dx[d], b = y + dy[d];
// 判断下一个位置是否出界或者是否已经填值
if(a<0 || a>=n || b<0 || b>=m || res[a][b]){
// 如果已经出界，就将方向旋转，这里d+1就是将方向旋转
// 对4取模是当最后一个方向时，加一就会超出数组下标，同时也为了实现循环数组
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
}
// 最后将下一个位置赋值给x, y
x = a, y = b;
}
// 打印结果
for(int i = 0; i < n; i ++ ){
for(int j = 0; j < m; j ++ ){
cout << res[i][j] << ' ';
}
cout << endl;
}
return 0;
}