👑作者主页：@进击的安度因
🏠学习社区：进击的安度因（个人社区）
📖专栏链接：每日挠头算法题
如果无聊的话，就来逛逛 我的博客栈 吧! 🌹
一、题目描述
链接：756. 蛇形矩阵
输入两个整数 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
二、思路讲解
蛇形矩阵，就是将数字以 回字形 填充到 二维数组 中，比如这样：
我们把 二维数组的行 看做 x轴，二维数组的列 看做 y轴。
结合数轴，我们其实可以发现蛇形矩阵填数的规律：从左上角第一个元素开始，先向右填，碰边；向下填，碰边；向左填，碰边；向上填，碰到已经填过的位置，退回原位；向右填 … 之后就是重复上面的规律来填充。
通过规律可以发现 蛇形矩阵 填数的其实是和 x, y 两个轴是息息相关的，我们将数据的坐标记为 (x, y)：
- 向右走：
(x, y) --> (x, y + 1)，纵坐标 + 1 - 向下走：
(x, y) --> (x + 1, y)，横坐标 + 1 - 向左走：
(x, y) --> (x, y - 1)，纵坐标 - 1 - 向上走：
(x, y) --> (x - 1, y)，横坐标 - 1
而上面四种移动在 题目中的具体表现 就像下面这样：
-
x不动 -x = 0，y向右移 -y + 1 -
y不动 -y = 0，x向下移 -x + 1 -
x不动 -x = 0，y向左移 -y - 1 -
y不动 -y = 0，x向上移 -x - 1
所以 x 和 y 的坐标变化就分别有 4 种。便可以把这些移动方式存入数组：dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 }。
从开始填数到填数完成需要改变很多次方向，那么什么情况需要改变填数方式？
- 填数越过左边界
- 填数越过右边界
- 填数越过上边界
- 填数越过下边界
- 填数位置已有数据
第五点 是最需要注意的，其实后面大多都是第五种情况，前四种情况基本只会在 最外一圈 用到。
在里层 碰到填过的数据 就得 “回退并拐弯” ，以免覆盖填过的数据。
到这儿主题思路其实已经讲完了，下面再讲一下细节：
如果坐标 x 或 y “飙错位置” ，如何把它 “拉回正确位置” ？可以用 a ，b 变量分别记录当前坐标在移动后是否超出范围，重新调整 移动方法 ，实际上就是重新选取 dx 或 dy 数组中 合适的元素 ，然后重新计算 a 和 b ，将坐标 拉回来 ，做出正确调整，再将 a 和 b 赋给 x 和 y 。文章来源：https://www.toymoban.com/news/detail-780705.html
下面我们看看代码怎么写。文章来源地址https://www.toymoban.com/news/detail-780705.html
三、代码实现
#include <iostream>
using namespace std;
const int N = 110;
// 全局中定义数组，元素默认初始化为0
int q[N][N];
int n, m;
int main()
{
cin >> n >> m;
int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };
// 起始 x 和 y 在 (0, 0)，并且 d 为 0，对应着 x 不动，y 往右走
int x = 0, y = 0, d = 0;
for (int i = 1; i <= n * m; i++)
{
q[x][y] = i;
// 计算 a, b 的下一个位置
int a = x + dx[d], b = y + dy[d];
// 判断是否超限
// 这里 q[a][b] 其实有一层妙用，由于全局数组是被初始化 0 的，
// 只要填过数，q[a][b] 就必定为真
if (a < 0 || a >= n || b < 0 || b >= m || q[a][b])
{
// 移动到下一个位置，% 4 获取 [0, 3] 下标
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
}
// 将正确的 a b 赋给 x y
x = a, y = b;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cout << q[i][j] << " ";
}
cout << endl;
}
return 0;
}
到了这里，关于【每日挠头算法题】Acwing 756. 蛇形矩阵 —— 巧妙解法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
