[1007] 魔法少女小Scarlet

题意

初始有一个 n*n 矩阵，按行填入 1..n^2。接下来多次把某个奇数阶子矩阵顺时针或逆时针旋转 90 度，输出最终矩阵。

思路

旋转时不能一边读原矩阵一边写回原位置，否则后面的格子会读到已经被覆盖的新值。稳妥做法是：

先复制出要旋转的子矩阵 block；
根据旋转方向生成 rotated；
再把 rotated 写回原矩阵。

对于边长为 size 的子矩阵：

顺时针：new[row][col] = old[size-1-col][row]
逆时针：new[row][col] = old[col][size-1-row]

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：二维矩阵可用列表嵌套列表保存。
/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：二维列表应逐行创建，避免多行引用同一个列表。
row[left:left+size] 可以复制一段连续列。
切片赋值 grid[top+row][left:left+size] = rotated[row] 可以整段写回。

代码

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
38def rotate_square(top, left, size, clockwise):
    block = [row[left:left + size] for row in grid[top:top + size]]

    if clockwise:
        rotated = [
            [block[size - 1 - col][row] for col in range(size)]
            for row in range(size)
        ]
    else:
        rotated = [
            [block[col][size - 1 - row] for col in range(size)]
            for row in range(size)
        ]

    for row in range(size):
        grid[top + row][left:left + size] = rotated[row]


n, m = map(int, input().split())
grid = []
value = 1

for _ in range(n):
    row = []
    for _ in range(n):
        row.append(value)
        value += 1
    grid.append(row)

for _ in range(m):
    x, y, r, z = map(int, input().split())
    size = 2 * r + 1
    top = x - r - 1
    left = y - r - 1
    rotate_square(top, left, size, z == 0)

for row in grid:
    print(*row)

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71/**
 * 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-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;

int n, m;
int grid[MAXN][MAXN];    // 原始矩阵
int tmp[MAXN][MAXN];     // 临时存储要旋转的子矩阵
int rotated[MAXN][MAXN]; // 旋转后的子矩阵

// 旋转子矩阵：左上角 (top,left)，边长 size，clockwise=1 表示顺时针
void rotate_square(int top, int left, int size, int clockwise) {
    // 1. 复制子矩阵到 tmp
    for (int i = 0; i < size; i++)
        for (int j = 0; j < size; j++)
            tmp[i][j] = grid[top + i][left + j];

    // 2. 旋转到 rotated
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (clockwise)
                rotated[i][j] = tmp[size - 1 - j][i];     // 顺时针
            else
                rotated[i][j] = tmp[j][size - 1 - i];     // 逆时针
        }
    }

    // 3. 写回原矩阵
    for (int i = 0; i < size; i++)
        for (int j = 0; j < size; j++)
            grid[top + i][left + j] = rotated[i][j];
}

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

    cin >> n >> m;

    // 初始化矩阵：按行填入 1..n^2
    int val = 1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            grid[i][j] = val++;

    // 执行 m 次旋转
    for (int t = 0; t < m; t++) {
        int x, y, r, z;
        cin >> x >> y >> r >> z;
        int size = 2 * r + 1;
        int top  = x - r - 1; // 题目坐标从 1 开始，转为 0 基
        int left = y - r - 1;
        rotate_square(top, left, size, z == 0);
    }

    // 输出
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << grid[i][j] << " ";
        cout << "\n";
    }

    return 0;
}

复杂度

每次旋转边长为 2r+1 的子矩阵，时间复杂度是 $O(r^2)$ 。总空间除原矩阵外，需要一个子矩阵副本。

总结

矩阵旋转题先复制原子矩阵，再按坐标公式生成新矩阵。这样最不容易被原地覆盖问题干扰。

[1007] 魔法少女小Scarlet

目录

题意

思路

Python 知识

代码

复杂度

总结