1886. Determine Whether Matrix Can Be Obtained By Rotation

📘 題目敘述

給你兩個 n x n 的二元矩陣 mat 和 target。

如果可以透過將 mat 每次旋轉 90 度，讓它變成和 target 完全相同，請回傳 true；否則回傳 false。

條件限制

n == mat.length == target.length
n == mat[i].length == target[i].length
1 <= n <= 10
mat[i][j] 和 target[i][j] 都只會是 0 或 1

🧠 解題思路

這題的想法很直接。

因為矩陣每次只能旋轉 90 度，而一個正方形矩陣最多轉四次就會回到原狀，所以我只要檢查：

原本的 mat
轉 90 度後
轉 180 度後
轉 270 度後

這四種情況裡，有沒有任何一次剛好等於 target。

所以我把整題拆成兩部分：

先寫一個 rotate 函式，專門把矩陣順時針轉 90 度
在主函式裡最多檢查四次，每次先比對，再決定要不要繼續旋轉

這樣就可以把所有可能情況都檢查完。

所有變數

mat：輸入矩陣，也是主函式裡每次旋轉後要拿來比對的矩陣
target：目標矩陣
v：傳進 rotate 的矩陣
n：矩陣邊長
now：旋轉後的新矩陣

🪜 主要流程步驟

1. 先寫一個 rotate 函式，把矩陣順時針旋轉 `90` 度

vector<vector<int>> rotate(vector<vector<int>>& v) {
    ...
}

這個函式的目的是：

輸入一個 n x n 矩陣
回傳它順時針旋轉 90 度後的新矩陣

我這裡沒有直接原地旋轉，而是另外開一個 now 來放旋轉後的結果。

2. 旋轉公式是 `now[i][j] = v[j][n - 1 - i]`

now[i][j] = v[j][n - 1 - i];

這一行是整個旋轉函式的核心。

它表示：

旋轉後位置 (i, j) 的值
來自原本矩陣的 (j, n - 1 - i)

這樣的對應就是順時針轉 90 度的標準位置變換。

例如原本最左下角的元素，旋轉後會跑到最左上那排；
原本最左上角的元素，旋轉後會跑到最右上角。

3. 在主函式裡，最多檢查四次

for (int i = 0; i < 4; i++) {
    if (mat == target) {
        return true;
    }
    mat = rotate(mat);
}

這裡我做的事情是：

先檢查目前的 mat 是否已經等於 target
如果相等，直接回傳 true
如果還不相等，就把 mat 旋轉一次，再繼續下一輪

因為正方形矩陣轉四次一定會回到原本的樣子，所以檢查四輪就已經把所有可能旋轉狀況看完了。

4. 為什麼要先比對、再旋轉

if (mat == target) {
    return true;
}
mat = rotate(mat);

這個順序代表我檢查的是：

第 0 次旋轉：原本的 mat
第 1 次旋轉：轉 90 度後
第 2 次旋轉：轉 180 度後
第 3 次旋轉：轉 270 度後

如果一開始就先旋轉，再比對，就會漏掉「原本就已經等於 target」這種情況。

所以這裡一定是先比，再轉。

5. 如果四次都不相等，就回傳 `false`

return false;

如果整個迴圈跑完都沒有提早回傳 true，代表：

原矩陣
轉 90 度
轉 180 度
轉 270 度

都無法變成 target。

所以答案就是 false。

⏱️ 複雜度

設 n = mat.length。

時間複雜度：O(n^2)
每次旋轉需要 O(n^2)，總共最多做 4 次，常數忽略後仍為 O(n^2)。
空間複雜度：O(n^2)
rotate 中額外建立了一個 n x n 的矩陣 now。

💻 程式碼實作

class Solution {
public:
    vector<vector<int>> rotate(vector<vector<int>>& v) {
        int n = v.size();
        vector<vector<int>> now(n, vector<int>(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                now[i][j] = v[j][n - 1 - i];
            }
        }
        return now;
    }
    bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
        for (int i = 0; i < 4; i++) {
            if (mat == target) {
                return true;
            }
            mat = rotate(mat);
        }
        return false;
    }
};

🔗 題目連結

https://leetcode.com/problems/determine-whether-matrix-can-be-obtained-by-rotation/