Given two n x n binary matrices mat and target, return true if it is possible to make mat equal to target by rotating mat in 90-degree increments, or false otherwise.
Example 1:
Input: mat = [[0,1],[1,0]], target = [[1,0],[0,1]] Output: true Explanation: We can rotate mat 90 degrees clockwise to make mat equal target.
Example 2:
Input: mat = [[0,1],[1,1]], target = [[1,0],[0,1]] Output: false Explanation: It is impossible to make mat equal to target by rotating mat.
Example 3:
Input: mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]] Output: true Explanation: We can rotate mat 90 degrees clockwise two times to make mat equal target.
Constraints:
n == mat.length == target.lengthn == mat[i].length == target[i].length1 <= n <= 10mat[i][j]andtarget[i][j]are either0or1.
Solution: Simulation
Time complexity: O(n2)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) { const int n = mat.size(); auto rot = [n](vector<vector<int>>& mat) { for (int i = 0; i < n; ++i) for (int j = i; j < n; ++j) swap(mat[i][j], mat[j][i]); for (int j = 0; j < n; j++) for (int i = 0; i < n / 2; ++i) swap(mat[i][j], mat[n - i - 1][j]); return mat; }; for (int i = 0; i < 4; ++i) if (rot(mat) == target) return true; return false; } }; |