[NOIP2014]螺旋矩阵

题目描述

给定 $n$ ，按“前进/右转”规则生成 $n \times n$ 螺旋矩阵（从左上角开始，依次填入 $1\dots n^2$ ）。输入 $n,i,j$ ，输出第 $i$ 行第 $j$ 列的数。

数据范围： $1 \le n \le 30000$ 。

思路

螺旋路线由外到内是一圈圈同心方环，每圈按“上→右→下→左”走完。先由 $\min(i-1,j-1,n-i,n-j)$ 定位目标格所在圈层 $k$ ，再求和前 $k$ 层完整圈的格子数，最后按四条边判断段内偏移，直接算出答案， $O(n)$ 时间、 $O(1)$ 空间。

参考代码

Python 版：

python

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
47#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 10:41
# update_at: 2026-10-02 10:41

import sys

size = 0  # 矩阵边长 n，layer 系列函数都要用它换算边界


def layer(row: int, col: int) -> int:
    """(row, col) 所在的圈层号：0 表示最外圈，中心点所在层为 n//2。"""
    return min(row - 1, col - 1, size - row, size - col)


def offset_on_layer(row: int, col: int, k: int) -> int:
    """(row, col) 是第 k 层按行进顺序的第几个格子（0 起），按四条边分四段累加。"""
    side = size - 2 * k       # 第 k 层的边长
    top_len = side - 1        # 第 k 层上边的格子数（不含下个转角）
    if row - 1 == k:          # 上边：从左到右
        return col - (k + 1)
    if size - col == k:       # 右边：从上到下
        return top_len + (row - (k + 1))
    if size - row == k:       # 下边：从右到左
        return 2 * top_len + (size - k - col)
    return 3 * top_len + (size - k - row)  # 左边：从下到上


def spiral_value(row: int, col: int) -> int:
    """第 row 行第 col 列格子里的数：外圈完整层的格子总数 + 本层内的行进偏移。"""
    k = layer(row, col)
    # 前 k 层（即第 0..k-1 层）的格子总数：每层 4*边长-4，边长从 size 每层减 2
    full = sum(4 * (size - 2 * m) - 4 for m in range(k))
    return full + offset_on_layer(row, col, k) + 1


def solve() -> None:
    global size
    n, i, j = map(int, sys.stdin.buffer.read().split())
    size = n
    print(spiral_value(i, j))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
47
48
49/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 15:14
 * update_at: 2026-10-06 15:14
 */

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

ll n, i, j;

// 计算 (row, col) 在螺旋矩阵中的值，利用圈层分解，O(1) 定位
ll spiral_value(ll row, ll col) {
    // 圈层号 k：到四条边界的最近距离，外圈为 0
    ll k = min(row - 1, min(col - 1, min(n - row, n - col)));
    // 前 k 层完整圈的格子总数
    ll full = 0;
    for (ll m = 0; m < k; ++m) {
        full += 4 * (n - 2 * m) - 4;
    }
    // 第 k 层的边长与上边格数（不含转角）
    ll side = n - 2 * k;
    ll top = side - 1;
    // 判断目标格落在第 k 层的哪条边上，累加段内偏移
    ll offset;
    if (row - 1 == k) {          // 上边，从左到右
        offset = col - (k + 1);
    } else if (n - col == k) {   // 右边，从上到下
        offset = top + (row - (k + 1));
    } else if (n - row == k) {   // 下边，从右到左
        offset = 2 * top + (n - k - col);
    } else {                     // 左边，从下到上
        offset = 3 * top + (n - k - row);
    }
    return full + offset + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> i >> j;
    cout << spiral_value(i, j) << '\n';
    return 0;
}

目录

题目描述

思路

参考代码