leetcode 130. 被围绕的区域

题解

bfs 广度优先搜索,首先把边界上出现的 O 以及相连的 O 置为 S,然后遍历二维矩阵 boardO 置为 X, S 置为 O

示例代码(go)

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
func solve(board [][]byte)  {
m, n := len(board), 0
if m > 0 {
n = len(board[0])
}
for j := 0; j < n; j++ {
if board[0][j] == 'O' {
bfs(board, m, n, 0, j)
}
}
for i := 1; i < m-1; i++ {
if board[i][0] == 'O' {
bfs(board, m, n, i, 0)
}
if board[i][n-1] == 'O' {
bfs(board, m, n, i, n-1)
}
}
for j := 0; j < n; j++ {
if board[m-1][j] == 'O' {
bfs(board, m, n, m-1, j)
}
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if board[i][j] == 'S' {
board[i][j] = 'O'
} else if board[i][j] == 'O' {
board[i][j] = 'X'
}
}
}
}

func bfs(board [][]byte, m, n, i, j int) {
if board[i][j] == 'O' {
board[i][j] = 'S'
}
if i-1 >= 0 && board[i-1][j] == 'O' {
bfs(board, m, n, i-1, j)
}
if i+1 < m && board[i+1][j] == 'O' {
bfs(board, m, n, i+1, j)
}
if j-1 >= 0 && board[i][j-1] == 'O' {
bfs(board, m, n, i, j-1)
}
if j+1 < n && board[i][j+1] == 'O' {
bfs(board, m, n, i, j+1)
}
}