Formatted question description: https://leetcode.ca/all/1886.html
1886. Determine Whether Matrix Can Be Obtained By Rotation
Level
Easy
Description
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.length
n == mat[i].length == target[i].length
1 <= n <= 10
mat[i][j]
andtarget[i][j]
are either0
or1
.
Solution
Let rotate
be the state of mat
after rotating 90 degrees clockwise. For 0 <= i < n
and 0 <= j < n
, there is rotate[j][n - 1 - i] = mat[i][j]
. Since rotating the matrix 4 times makes the matrix recover to the original state, the matrix can be rotated at most 4 times. Therefore, rotate the matrix 1, 2, 3 and 4 times respecitvely, and for each state, check whether the state is the same as target
. If there exists one state that is the same as target
, return true
. Otherwise, return false
.
class Solution {
public boolean findRotation(int[][] mat, int[][] target) {
int n = mat.length;
int[][] rotate = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
rotate[i][j] = mat[i][j];
}
for (int count = 1; count <= 4; count++) {
int[][] temp = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
temp[j][n - 1 - i] = rotate[i][j];
}
rotate = temp;
if (areSame(rotate, target))
return true;
}
return false;
}
public boolean areSame(int[][] mat, int[][] target) {
int n = mat.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] != target[i][j])
return false;
}
}
return true;
}
}