130 Surrounded Regions

130. Surrounded Regions

1. Question

Given a 2D board containing'X'and'O'(the letter O), capture all regions surrounded by'X'.
A region is captured by flipping all'O's into'X's in that surrounded region.
For example,
1
X X X X
2
X O O X
3
X X O X
4
X O X X
Copied!
After running your function, the board should be:
1
X X X X
2
X X X X
3
X X X X
4
X O X X
Copied!

2. Implementation

(1) BFS
1
class Solution {
2
public void solve(char[][] board) {
3
if (board == null || board.length == 0) {
4
return;
5
}
6
7
int m = board.length, n = board[0].length;
8
int[][] directions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
9
10
for (int i = 0; i < m; i++) {
11
fill(board, i, 0, directions);
12
fill(board, i, n - 1, directions);
13
}
14
15
for (int j = 0; j < n; j++) {
16
fill(board, 0, j, directions);
17
fill(board, m - 1, j, directions);
18
}
19
20
for (int i = 0; i < m; i++) {
21
for (int j = 0; j < n; j++) {
22
if (board[i][j] == '#') {
23
board[i][j] = 'O';
24
}
25
else if (board[i][j] == 'O') {
26
board[i][j] = 'X';
27
}
28
}
29
}
30
}
31
32
public void fill(char[][] board, int row, int col, int[][] directions) {
33
if (board[row][col] == 'O') {
34
board[row][col] = '#';
35
Queue<int[]> queue = new LinkedList<>();
36
queue.add(new int[] {row, col});
37
38
while (!queue.isEmpty()) {
39
int[] cell = queue.remove();
40
int curRow = cell[0], curCol = cell[1];
41
42
for (int[] direction : directions) {
43
int nextRow = curRow + direction[0];
44
int nextCol = curCol + direction[1];
45
46
if (isValid(board, nextRow, nextCol)) {
47
board[nextRow][nextCol] = '#';
48
queue.add(new int[] {nextRow, nextCol});
49
}
50
}
51
}
52
}
53
}
54
55
public boolean isValid(char[][] board, int row, int col) {
56
return row >= 0 && row < board.length && col >= 0 && col < board[0].length && board[row][col] == 'O';
57
}
58
}
Copied!

3. Time & Space Complexity

BFS: 时间复杂度O(mn), 空间复杂度O(mn), m和n分别为board的行数和列数