@shachopin/

# Surrounded Regions

## No description

Files
• Main.java
• jdt.ls-java-project
Main.java
```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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
```
```class Main {
public static void main(String[] args) {
System.out.println("Hello world!");
}
}

public class Solution {
/*
* @param board: board a 2D board containing 'X' and 'O'
* @return: nothing
*/
//类似number of islands
//二维
//flood fill
//单源
//不在乎target, 因为不是shortest path问题
//重用题目给的2D array
//二重循环
int[] dx = new int[]{0, -1, 1, 0};
int[] dy = new int[]{1, 0, 0, -1};
public void surroundedRegions(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}

int rows = board.length;
int cols = board[0].length;

for (int i = 0; i < rows; i++) {
// if (board[i][0] == 'X') {
//     continue;
// }
bfs(board, i, 0);

// if (board[i][cols - 1] == 'X') {
//     continue;
// }
bfs(board, i, cols - 1);
}

for (int i = 0; i < cols; i++) {
// if (board[0][i] == 'X') {
//     continue;
// }
bfs(board, 0, i);

// if (board[rows - 1][i] == 'X') {
//     continue;
// }
bfs(board, rows - 1, i);
}

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == 'W') {
board[i][j] = 'O';
} else {
board[i][j] = 'X';
}
}
}
}

private void bfs(char[][] board, int x, int y) {
if (board[x][y] == 'X') {
return;
}
//is 'O'
queue.offer(new Point(x, y));
board[x][y] = 'W';
while (!queue.isEmpty()) {
Point curPoint = queue.poll();
for (int i = 0; i < 4; i++) {
int nx = curPoint.x + dx[i];
int ny = curPoint.y + dy[i];
if (nx < 0 || nx >= board.length || ny < 0 || ny >= board[0].length) {
continue;
}
if (board[nx][ny] != 'O') {
continue;
}

queue.offer(new Point(nx, ny));
board[nx][ny] = 'W';
}
}

}
}

class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}```