leetcode 130. 被围绕的区域

题目描述

给定一个二维的矩阵,包含 ‘X’ 和 ‘O’(字母 O)。
找到所有被 ‘X’ 围绕的区域,并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例:


X X X X
X O O X
X X O X
X O X X

运行你的函数后,矩阵变为:


X X X X
X X X X
X X X X
X O X X

解释:
被围绕的区间不会存在于边界上,换句话说,任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上,或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。

题解

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)
}
}