【深基5.习6】蛇形方阵

解题思路

从左上角开始按右、下、左、上四个方向填数。若下一格越界或已经填过，就顺时针换方向。

正确性说明

从当前方向尽量延伸，到边界后转弯会沿外圈再逐层进入内圈，恰好形成顺时针螺旋。每次填入一个未填格，共 n² 次覆盖全部格子。

易错点

每个数占三列，用 setw(3)，不要在数后额外加空格。

复杂度

时间 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[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}, x = 0, y = 0, d = 0;
    for (int k = 1; k <= n * n; k++) {
        a[x][y] = k;
        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 v : r)
            cout << setw(3) << v;
        cout << "\n";
    }
    return 0;
}