前言
持续更新了
正文
问题来源
本问题来自leetcode上的130题。
问题描述
给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。
找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
示例 1:
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
分析：
记录从边上能够访问的位置，若不能到达则标记为’X’
func solve(board [][]byte) {
if board == nil || 0 == len(board) || 0 == len(board[0]) {
return
}
v := make([][]bool, len(board))
for i := 0; i < len(board); i++ {
v[i] = make([]bool, len(board[0]))
}
for i := 0; i < len(board[0]); i++ {
dfs(board, v, 0, i)
dfs(board, v, len(board)-1, i)
}
for i := 0; i < len(board); i++ {
dfs(board, v, i, 0)
dfs(board, v, i, len(board[0])-1)
}
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if !v[i][j] {
board[i][j] = 'X'
}
}
}
}
func dfs(board [][]byte, visit [][]bool, i, j int) {
if i >= len(board) || i < 0 || j >= len(board[0]) || j < 0 || visit[i][j] || board[i][j] == 'X' {
return
}
visit[i][j] = true
dfs(board, visit, i, j-1)
dfs(board, visit, i-1, j)
dfs(board, visit, i, j+1)
dfs(board, visit, i+1, j)
}
其实可以不用额外空间来记录是否能够访问，能够访问则标记为不为’X’或’O’的标记
func solve(board [][]byte) {
if len(board) == 0 {
return
}
for i := 0; i < len(board[0]); i++ { // 围绕着周围做Bfs
dfs(0, i, board)
dfs(len(board) - 1, i, board)
}
for i := 0; i < len(board); i++ {
dfs(i, 0, board)
dfs(i, len(board[0]) - 1, board)
}
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if board[i][j] == 'V' {
board[i][j] = 'O'
} else {
board[i][j] = 'X'
}
}
}
}
func dfs(i int, j int, board[][]byte) {
if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) {
return
} else if board[i][j] == 'X' || board[i][j] == 'V' { //已访问过或者不等于O
return
}
board[i][j] = 'V'
dfs(i - 1, j, board)
dfs(i + 1, j, board)
dfs(i, j - 1, board)
dfs(i, j + 1, board)
}
总结：
勤思考。
结语
不管怎么样好好加油。
