蛇形矩阵 网格题

1. 定坐标，找方向。

本题有4个方向，可以用偏移量的方式来表示，eg:

          (-1, 0)
             ↑
(0, 1)  ←  [x,y]  →  (1, 0)
             ↓
          (0, -1)
// 从(-1, 0)开始，顺时针给每个偏移量标号：0，1，2，3

移动后的坐标可表示为 (x,y) + (dx, dy)
移动方向的依次为：1→2→3→0，d = (d + 1) % 4

2. “撞墙”

1. a越界
2. b越界
3. q[a][b]已经走过
   if(a < 0 || a >= n || b < 0 || b >= m || q[a][b])

C++ 代码

#include <iostream>

using namespace std;

const int N = 110;

int n, m;
int q[N][N];

int main() {
    cin >> n >> m;

    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    int x = 0, y = 0, d = 1;
    for(int i = 1; i <= n * m; i++) {
        q[x][y] = i;
        int a = x + dx[d], b = y + dy[d];
        if(a < 0 || a >= n || b < 0 || b >= m || q[a][b]) {
            d = (d + 1) % 4;
            a = x + dx[d];
            b = y + dy[d];
        }
        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;
}