被围绕的区域
这题别正着想“哪些 O 会被吃掉”，而要反着想“哪些 O 一定不能被吃掉”。
问题描述
LeetCode 130 - 被围绕的区域
给定一个二维矩阵，包含’X’和’O’。找到所有被’X’围绕的区域，并将这些区域里所有的’O’用’X’填充。被围绕的区域不会存在于边界上。
输入: 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’开始，标记所有连通的’O’
- DFS/BFS：从边界’O’进行DFS/BFS
- 标记保留：边界连通的’O’标记为临时字符
- 填充转换：未标记的’O’变为’X’，临时字符恢复为’O’
为什么要从边界反推
真正不会被包围的 'O'，一定满足：
- 它在边界上，或者
- 它能连到边界上的
'O'
所以与其去猜哪些 'O' 会被翻掉，不如先把所有“安全区”从边界出发整块标出来。
最后剩下那些没被保护到的 'O'，才是应该翻成 'X' 的部分。
Go 代码
Go 实现
func solve(board [][]byte) {
if len(board) == 0 {
return
}
rows, cols := len(board), len(board[0])
var dfs func(int, int)
dfs = func(r, c int) {
if r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != 'O' {
return
}
board[r][c] = '#'
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
}
// 从边界DFS
for r := 0; r < rows; r++ {
if board[r][0] == 'O' {
dfs(r, 0)
}
if board[r][cols-1] == 'O' {
dfs(r, cols-1)
}
}
for c := 0; c < cols; c++ {
if board[0][c] == 'O' {
dfs(0, c)
}
if board[rows-1][c] == 'O' {
dfs(rows-1, c)
}
}
// 转换
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if board[r][c] == 'O' {
board[r][c] = 'X'
} else if board[r][c] == '#' {
board[r][c] = 'O'
}
}
}
}易错点
这题最容易错的地方，是边界扫描不完整或者标记字符处理不干净。
- 四条边都要扫到，不能只扫两条。
- 临时标记字符要和原字符集区分开，比如用
#。 - 最后别忘了做两次转换：
O -> X，# -> O。 - 这题和岛屿数量一样，本质上也是网格连通块问题。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(M×N) | 遍历所有格子 |
| 空间复杂度 | O(M×N) | 递归栈（最坏情况） |