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
| class Solution {
int m, n;
String[] chessboard;
public int flipChess(String[] chessboard) {
m = chessboard.length;
n = chessboard[0].length();
this.chessboard = chessboard;
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (chessboard[i].charAt(j) == '.') {
ans = Math.max(ans, bfs(i, j));
}
}
}
return ans;
}
private int bfs(int i, int j) {
Deque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{i, j});
char[][] g = new char[m][];
for (int k = 0; k < m; ++k) {
g[k] = chessboard[k].toCharArray();
}
g[i][j] = 'X';
int ans = 0;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
i = cur[0];
j = cur[1];
for (int a = -1; a <= 1; ++a) {
for (int b = -1; b <= 1; ++b) {
if (a == 0 && b == 0) continue;
int x = i + a, y = j + b;
while (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 'O') {
x += a;
y += b;
}
if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 'X') {
x -= a;
y -= b;
ans += Math.max(Math.abs(x - i), Math.abs(y - j));
while (x != i || y != j) {
g[x][y] = 'X';
queue.offer(new int[]{x, y});
x -= a;
y -= b;
}
}
}
}
}
return ans;
}
}
|
wechat
