AcWing 756. 蛇形矩阵 - 核心逻辑时间复杂度 T(n) = O(n); 注释详细
原题链接
简单
作者:
624
,
2021-05-31 20:56:04
,
所有人可见
,
阅读 292
#include <iostream>
using namespace std;
bool isHorizontal(int dir) {
return dir % 2 == 0;
}
int main() {
// 输入
int n, m; // n 行, m 列, n <=> x 轴, m <=> y 轴
cin >> n >> m;
// 初始化
int arr[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
arr[i][j] = 0;
}
}
// 计算
int directions[4][2] = { // 贪吃蛇行进方向
{0, 1}, // 右
{1, 0}, // 下
{0, -1}, // 左
{-1, 0}, // 上
};
int cur_dir = 0; // 当前方向, 初始值为右
int step = 0; // 当前方向行进步长
int x = 0, y = 0; // 当前位置坐标
for (int i = 1; i < n * m + 1; i++) {
arr[x][y] = i;
if (isHorizontal(cur_dir)) {
if (step == m - 1) { // 水平方向边界判断. 更新状态 (新的行进方向, 新的步长)
cur_dir = ++cur_dir % 4;
step = 1;
} else {
step++;
}
} else {
if (step == n - 1) { // 垂直方向边界判断. 更新状态 (新的行进方向, 新的步长)
cur_dir = ++cur_dir % 4;
step = 1;
} else {
step++;
}
}
if (arr[x + directions[cur_dir][0]][y + directions[cur_dir][1]] !=
0) { // 该方向的下一个位置已经被赋值了, 说明"撞到自己"了. 更新状态 (新的行进方向, 新的步长)
cur_dir = ++cur_dir % 4;
step = 1;
}
// 贪吃蛇行进
x += directions[cur_dir][0];
y += directions[cur_dir][1];
}
// 输出
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << arr[i][j] << " ";
}
cout << endl;
}
return 0;
}