旋转矩阵-判断旋转角度

Posted on

题目描述

题目链接：N诺/DreamJudge 1377

输入两个 n 阶矩阵（n≤9），判断第二个是否是第一个旋转得到的。如果是，输出旋转角度（0、90、180、270 中最小的那个），否则输出 -1。

  • 多组测试数据
  • 矩阵元素间用任意空格分隔，矩阵间用任意回车分隔

核心思路

旋转矩阵的本质是坐标变换。与其推导 90°/180°/270° 各自的计算公式，不如只写一个 rotate90 函数，然后反复调用它：

  • 旋转一次 → 90°
  • 旋转两次 → 180°
  • 旋转三次 → 270°

省去推导三套公式的麻烦，代码量也少一半。

旋转 90° 的原理

顺时针旋转 90° 时，原矩阵中位置 (i, j) 的元素会跑到新矩阵的 (j, n-1-i) 位置：

1
原矩阵 (i, j)  →  旋转后 (j, n-1-i)

直观理解：原来的行号变成新列号，原来的列号倒过来变成新行号。

1
2
3
4
5
6
7
8
以 3×3 为例：
1 2 3      7 4 1
4 5 6  →   8 5 2
7 8 9      9 6 3

(0,0)=1 → (0,2)=1  原第一行 → 新最后一列
(0,1)=2 → (1,2)=2  原第一行 → 新中间列
(0,2)=3 → (2,2)=3  原第一行 → 新第一列

rotate90 实现

1
2
3
4
5
6
7
8
9
vector<vector<int>> rotate90(vector<vector<int>> mtx, int n) {
    vector<vector<int>> rotate(n, vector<int>(n));
    for (int i = 0; i < mtx.size(); i++) {
        for (int j = 0; j < mtx[i].size(); j++) {
            rotate[j][n - i - 1] = mtx[i][j];  // ⚠️ 关键公式
        }
    }
    return rotate;
}

180° 和 270° 的处理技巧

不要单独写 rotate180 和 rotate270。在 rotate90 的基础上继续转就行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int check(vector<vector<int>> mtx1, vector<vector<int>> mtx2, int n) {
    if (isequal(mtx1, mtx2, n)) return 0;       // 0°

    vector<vector<int>> rot = rotate90(mtx1, n);
    if (isequal(rot, mtx2, n)) return 90;        // 90°

    rot = rotate90(rot, n);                       // ⚠️ 在90°基础上再转90° = 180°
    if (isequal(rot, mtx2, n)) return 180;

    rot = rotate90(rot, n);                       // ⚠️ 再转一次 = 270°
    if (isequal(rot, mtx2, n)) return 270;

    return -1;
}

每次 rotate90 返回一个新矩阵，不修改原矩阵。按 0→90→180→270 的顺序检查，天然保证输出的是最小角度。

⚠️ 关键坑点

  1. 旋转公式容易写反 — rotate[j][n-i-1] = mtx[i][j]，新矩阵的行是 j，列是 n-i-1。别写成 rotate[i][j] = mtx[j][n-i-1]。
  2. 每次 rotate90 传入的是上一次的结果 — 180° 是 rotate90(rot, n) 而不是 rotate90(mtx1, n)，否则会一直拿原始矩阵在转。
  3. isequal 的 n 不要越界 — 循环范围是 i < n 和 j < n。

完整代码模板

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
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> rotate90(vector<vector<int>> mtx, int n) {
    vector<vector<int>> rotate(n, vector<int>(n));
    for (int i = 0; i < mtx.size(); i++) {
        for (int j = 0; j < mtx[i].size(); j++) {
            rotate[j][n - i - 1] = mtx[i][j];
        }
    }
    return rotate;
}

bool isequal(vector<vector<int>> mtx1, vector<vector<int>> mtx2, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (mtx1[i][j] != mtx2[i][j]) {
                return false;
            }
        }
    }
    return true;
}

int check(vector<vector<int>> mtx1, vector<vector<int>> mtx2, int n) {
    if (isequal(mtx1, mtx2, n)) {
        return 0;
    }
    vector<vector<int>> rot = rotate90(mtx1, n);
    if (isequal(rot, mtx2, n)) {
        return 90;
    }
    rot = rotate90(rot, n);
    if (isequal(rot, mtx2, n)) {
        return 180;
    }
    rot = rotate90(rot, n);
    if (isequal(rot, mtx2, n)) {
        return 270;
    }
    return -1;
}

int main() {
    int n;
    while (cin >> n) {
        vector<vector<int>> mtx1(n, vector<int>(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> mtx1[i][j];
            }
        }
        vector<vector<int>> mtx2(n, vector<int>(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> mtx2[i][j];
            }
        }
        cout << check(mtx1, mtx2, n) << endl;
    }
}

总结

要点 说明
90° 旋转公式 rotate[j][n-i-1] = mtx[i][j]
180° 处理 rotate90(rotate90(mtx))，链式调用
270° 处理 rotate90(rotate90(rotate90(mtx)))
最小角度保证 按 0→90→180→270 顺序检查
时间复杂度 $O(n^2)$ per rotation