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
58
59
60
61
62
63
64
|
public class SurroundedRegions {
Queue<Pair> queue = new LinkedList<Pair>();
public void solve(char[][] board) {
if (board == null || board.length < 3 || board[0] == null || board[0].length < 3) {
return;
}
for (int i = 0; i < board.length; i++) {
if (board[i][0] == 'O') {
helper(board, i, 0);
}
if (board[i][board[0].length - 1] == 'O') {
helper(board, i, board[0].length - 1);
}
}
for (int i = 0; i < board[0].length; i++) {
if (board[0][i] == 'O') {
helper(board, 0, i);
}
if (board[board.length - 1][i] == 'O') {
helper(board, board.length - 1, i);
}
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == '#') {
board[i][j] = 'O';
}
}
}
}
private void helper(char[][] board, int i, int j) {
search(board, i, j);
while (!queue.isEmpty()) {
Pair p = queue.poll();
search(board, p.x + 1, p.y);
search(board, p.x - 1, p.y);
search(board, p.x, p.y + 1);
search(board, p.x, p.y - 1);
}
}
private void search(char[][] board, int i, int j) {
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O') {
return;
}
queue.add(new Pair(i, j));
board[i][j] = '#';
}
static class Pair {
Pair(int x, int y) {
this.x = x;
this.y = y;
}
int x, y;
}
}
|