题目描述#

给你一个 m x n 的矩阵 board，由 'X' 和 'O' 组成。将所有被 'X' 完全包围的 'O' 区域替换为 'X'。与棋盘边缘相连的 'O' 不算被围绕，不需要替换。

思路#

正面找"被围绕的区域"不好判断，反过来找"安全的 'O'“更直接——只要一个 'O' 与边缘的 'O' 相连，它就一定不会被捕获。

从四条边上所有的 'O' 出发，做 DFS 扩散，把能连通的 'O' 全部标记为临时占位符 '#'。扩散结束后，矩阵里剩余的 'O' 就是真正被围绕的区域，直接改成 'X'；而 '#' 是安全的，还原成 'O'。

遍历边缘时，先横向扫左右两列，再纵向扫上下两行，注意不要重复触发角落格子（重复调用无害，DFS 进去发现不是 'O' 直接返回）。

递归步骤图示#

以下面这个 4×4 棋盘为例：

初始状态：
X X X X
X O O X
X X O X
X O X X

第一步：扫描左右两列边缘

左列 board[0..3][0] 全是 X，DFS 进去直接返回。
右列 board[0..3][3] 全是 X，同理。

第二步：扫描上下两行边缘

上行 board[0][0..3] 全是 X，跳过。
下行扫到 board[3][1] = 'O'，发起 DFS：

dfs(3,1)  'O' → 标记为 '#'
  dfs(2,1)  'X'，返回
  dfs(4,1)  越界，返回
  dfs(3,0)  'X'，返回
  dfs(3,2)  'X'，返回

只有 board[3][1] 被标记，其余边缘格子均为 X，DFS 都直接返回。

扩散结束后：
X X X X
X O O X   ← 这三个 O 未连边缘，是被围绕的区域
X X O X
X # X X   ← # 是安全区

第三步：全局替换

• 剩余的 'O' → 'X'（被围绕，捕获）
• '#' → 'O'（安全区，还原）

最终结果：
X X X X
X X X X
X X X X
X O X X

知识边界#

• 这是"逆向标记"技巧：正面条件复杂时，先标记反面（安全区域），剩下的就是答案
• 临时占位符 '#' 的作用和岛屿题中的 '2' 一样，避免重复访问、区分最终状态
• DFS 从边缘出发而非从内部出发，是本题的核心思路转换

代码#

func solve(board [][]byte) {
    m := len(board)
    n := len(board[0])
    // 本题的思路是把边缘的0标记安全，对边缘的0进行扩散dfs
    var dfs func(int, int)
    dfs = func(i, j int) {
        if i < 0 || j < 0 || i >= m || j >= n || board[i][j] != 'O' {
            return
        }
        board[i][j] = '#'
        dfs(i-1, j)
        dfs(i+1, j)
        dfs(i, j-1)
        dfs(i, j+1)
    }

    // 先横着开始
    for i := 0; i < m; i++ {
        dfs(i, 0)
        dfs(i, n-1)
    }
    // 然后竖着来
    for j := 0; j < n; j++ {
        dfs(0, j)
        dfs(m-1, j)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == 'O' {
                board[i][j] = 'X'
            } else if board[i][j] == '#' {
                board[i][j] = 'O'
            }
        }
    }
}