[NOIP 2014 普及组] 螺旋矩阵

题意

给一个 n × n 的螺旋矩阵。

填数规则是：

从左上角 (1,1) 开始，先向右走；
如果前面还能走到没访问过的格子，就继续走；
否则右转；
直到所有格子都填完 $1..n^2$ 。

题目只问第 i 行第 j 列这个位置最终是多少。

思路

先看最直接的做法：真的开一个矩阵，然后按题目的走法一步一步模拟填数，最后输出 a[i][j]。

这个版本最容易理解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46#include <bits/stdc++.h>
using namespace std;

// brute.cpp：按题目描述直接模拟走螺旋。
// 只适合很小的 n，用来帮助理解题意并辅助对拍。
const int MAXN = 205;

int n, target_i, target_j;
int a[MAXN][MAXN];
bool vis[MAXN][MAXN];

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

bool inside(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= n;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> target_i >> target_j;

    int x = 1;
    int y = 1;
    int dir = 0;

    for (int val = 1; val <= n * n; val++) {
        a[x][y] = val;
        vis[x][y] = true;

        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (!inside(nx, ny) || vis[nx][ny]) {
            dir = (dir + 1) % 4;
            nx = x + dx[dir];
            ny = y + dy[dir];
        }
        x = nx;
        y = ny;
    }

    cout << a[target_i][target_j] << '\n';
    return 0;
}

但 n 最大到 30000，如果真的把整个矩阵都建出来，时间和空间都会太大。

关键是目标格子只会落在某一层“外框”上，我们没必要把整个矩阵都填出来。

设目标位置是 (i,j)，它所在的层数就是它离四条边的最小距离：

$layer = min(i-1, j-1, n-i, n-j)$

把这一层外框剥出来后，它左上角坐标是：

行：layer + 1
列：layer + 1

这一层的边长记为 $len = n - 2 * layer$ 。

这一层的起点编号

每往里走一层，外面会先被完整填掉一圈。

边长为 len 的这一层外框一共有：

$4 * (len - 1)$

个格子，但我们不需要一层层累加。更直接的是：

这一层左上角的编号等于前面所有外层格子数加一，也就是：

$start = 1 + 4 * layer * (n - layer)$

这个式子可以直接展开验证：

第 0 层起点是 1
第 1 层起点是 1 + 4(n-1)
第 2 层起点再往后跳一圈

分四条边讨论

知道了这一层的起点后，只要看 (i,j) 落在这层的哪一条边上。

如果在上边： $i == layer + 1$ 直接从左往右数，答案是
start + (j - (layer + 1))
如果在右边： $j == n - layer$ 先走完整条上边，再从上往下数，答案是
start + (len - 1) + (i - (layer + 1))
如果在下边： $i == n - layer$ 先走完上边和右边，再从右往左数，答案是
$start + 2 * (len - 1) + ((n - layer) - j)$
否则一定在左边：前三条边都走完后，再从下往上数，答案是
$start + 3 * (len - 1) + ((n - layer) - i)$

这样就能直接算出目标位置的编号，不需要真的构造整个矩阵。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35#include <bits/stdc++.h>
using namespace std;

long long n, i_pos, j_pos;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> i_pos >> j_pos;

    long long layer = min(min(i_pos - 1, j_pos - 1), min(n - i_pos, n - j_pos));
    long long top = layer + 1;
    long long left = layer + 1;
    long long bottom = n - layer;
    long long right = n - layer;
    long long len = n - 2 * layer;

    // start 表示这一层左上角格子的编号。
    long long start = 1 + 4LL * layer * (n - layer);

    long long ans;
    if (i_pos == top) {
        ans = start + (j_pos - left);
    } else if (j_pos == right) {
        ans = start + (len - 1) + (i_pos - top);
    } else if (i_pos == bottom) {
        ans = start + 2 * (len - 1) + (right - j_pos);
    } else {
        ans = start + 3 * (len - 1) + (bottom - i_pos);
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(1)$
空间复杂度： $O(1)$

总结

这题表面上是模拟，但真正要抓住的是“按层分解”。

只要先定位目标格子属于哪一层，再判断它在这一层的哪一条边上，就能把整题化成一个分段计算问题。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。