给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
示例 1：
输入：board = [["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'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。示例 2：
输入：board = [["X"]]
输出：[["X"]]提示：
- m == board.length
- n == board[i].length
- 1 <= m, n <= 200
- board[i][j] 为 ‘X’ 或 ‘O’
解题：
// 还差10个没通过官方解答：
1.深度优先搜索
var n, m int
func solve(board [][]byte) {
if len(board) == 0 || len(board[0]) == 0 {
return
}
n, m = len(board), len(board[0])
for i := 0; i < n; i++ {
dfs(board, i, 0)
dfs(board, i, m-1)
}
for i := 1; i < m-1; i++ {
dfs(board, 0, i)
dfs(board, n-1, i)
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if board[i][j] == 'A' {
board[i][j] = 'O'
} else if board[i][j] == 'O' {
board[i][j] = 'X'
}
}
}
}
func dfs(board [][]byte, x, y int) {
if x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O' {
return
}
board[x][y] = 'A'
dfs(board, x+1, y)
dfs(board, x-1, y)
dfs(board, x, y+1)
dfs(board, x, y-1)
}2.广度优先搜索
var (
dx = [4]int{1, -1, 0, 0}
dy = [4]int{0, 0, 1, -1}
)
func solve(board [][]byte) {
if len(board) == 0 || len(board[0]) == 0 {
return
}
n, m := len(board), len(board[0])
var queue [][]int
for i := 0; i < n; i++ {
if board[i][0] == 'O' {
queue = append(queue, []int{i, 0})
board[i][0] = 'A'
}
if board[i][m-1] == 'O' {
queue = append(queue, []int{i, m - 1})
board[i][m-1] = 'A'
}
}
for i := 1; i < m-1; i++ {
if board[0][i] == 'O' {
queue = append(queue, []int{0, i})
board[0][i] = 'A'
}
if board[n-1][i] == 'O' {
queue = append(queue, []int{n - 1, i})
board[n-1][i] = 'A'
}
}
for len(queue) > 0 {
cell := queue[0]
queue = queue[1:]
x, y := cell[0], cell[1]
for i := 0; i < 4; i++ {
mx, my := x+dx[i], y+dy[i]
if mx < 0 || my < 0 || mx >= n || my >= m || board[mx][my] != 'O' {
continue
}
queue = append(queue, []int{mx, my})
board[mx][my] = 'A'
}
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if board[i][j] == 'A' {
board[i][j] = 'O'
} else if board[i][j] == 'O' {
board[i][j] = 'X'
}
}
}
}