【例63.1】 蛇形填数

解题思路

从右上角开始向下填1，依次按下、左、上、右循环转向。下一格越界或已填就换方向，完成n²个数。

正确性说明

依题目给出的对应关系逐项处理，位置与原输入保持明确对应。每一步完成当前项的全部贡献，结束后得到所有位置或字符的目标结果。

易错点

起点和方向不同于常见左上顺时针螺旋；按样例右上向下。

复杂度

时间O(n²)，空间O(n²)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1}, x = 0, y = n - 1, d = 0;
    for (int v = 1; v <= n * n; v++) {
        a[x][y] = v;
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n || a[nx][ny]) {
            d = (d + 1) % 4;
            nx = x + dx[d];
            ny = y + dy[d];
        }
        x = nx;
        y = ny;
    }
    for (auto &r : a) {
        for (int j = 0; j < n; j++) {
            if (j)
                cout << " ";
            cout << r[j];
        }
        cout << "\n";
    }
    return 0;
}