![](https://img.shields.io/badge/分数-1337-4051B5?style=flat-square)
题目描述
给你一个二维 3 x 3
的矩阵 grid
,每个格子都是一个字符,要么是 'B'
,要么是 'W'
。字符 'W'
表示白色,字符 'B'
表示黑色。
你的任务是改变 至多一个 格子的颜色,使得矩阵中存在一个 2 x 2
颜色完全相同的正方形。
如果可以得到一个相同颜色的 2 x 2
正方形,那么返回 true
,否则返回 false
。
示例 1:
输入:grid = [["B","W","B"],["B","W","W"],["B","W","B"]]
输出:true
解释:
修改 grid[0][2]
的颜色,可以满足要求。
示例 2:
输入:grid = [["B","W","B"],["W","B","W"],["B","W","B"]]
输出:false
解释:
只改变一个格子颜色无法满足要求。
示例 3:
输入:grid = [["B","W","B"],["B","W","W"],["B","W","W"]]
输出:true
解释:
grid
已经包含一个 2 x 2
颜色相同的正方形了。
提示:
grid.length == 3
grid[i].length == 3
grid[i][j]
要么是 'W'
,要么是 'B'
。
解法
方法一:枚举
我们可以枚举每个 $2 \times 2$ 的正方形,统计黑色和白色的个数,如果两者个数不相等,那么就可以构造一个相同颜色的正方形,返回 true
。
否则,遍历结束后返回 false
。
时间复杂度 $O(1)$,空间复杂度 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def canMakeSquare(self, grid: List[List[str]]) -> bool:
for i in range(0, 2):
for j in range(0, 2):
cnt1 = cnt2 = 0
for a, b in pairwise((0, 0, 1, 1, 0)):
x, y = i + a, j + b
cnt1 += grid[x][y] == "W"
cnt2 += grid[x][y] == "B"
if cnt1 != cnt2:
return True
return False
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public boolean canMakeSquare(char[][] grid) {
final int[] dirs = {0, 0, 1, 1, 0};
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
int cnt1 = 0, cnt2 = 0;
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
cnt1 += grid[x][y] == 'W' ? 1 : 0;
cnt2 += grid[x][y] == 'B' ? 1 : 0;
}
if (cnt1 != cnt2) {
return true;
}
}
}
return false;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution {
public:
bool canMakeSquare(vector<vector<char>>& grid) {
int dirs[5] = {0, 0, 1, 1, 0};
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
int cnt1 = 0, cnt2 = 0;
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
cnt1 += grid[x][y] == 'W';
cnt2 += grid[x][y] == 'B';
}
if (cnt1 != cnt2) {
return true;
}
}
}
return false;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | func canMakeSquare(grid [][]byte) bool {
dirs := [5]int{0, 0, 1, 1, 0}
for i := 0; i < 2; i++ {
for j := 0; j < 2; j++ {
cnt1, cnt2 := 0, 0
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if grid[x][y] == 'W' {
cnt1++
} else {
cnt2++
}
}
if cnt1 != cnt2 {
return true
}
}
}
return false
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | function canMakeSquare(grid: string[][]): boolean {
const dirs: number[] = [0, 0, 1, 1, 0];
for (let i = 0; i < 2; ++i) {
for (let j = 0; j < 2; ++j) {
let [cnt1, cnt2] = [0, 0];
for (let k = 0; k < 4; ++k) {
const [x, y] = [i + dirs[k], j + dirs[k + 1]];
if (grid[x][y] === 'W') {
++cnt1;
} else {
++cnt2;
}
}
if (cnt1 !== cnt2) {
return true;
}
}
}
return false;
}
|