被围绕的区域：从边界反向搜索

核心结论#

直接寻找“被包围的区域”不容易，但边界上的 O 以及与它连通的 O 一定不能被填充。先从四条边界执行深度优先搜索并临时标记安全区域，再把其余 O 改成 X，最后恢复标记即可。

问题#

矩阵只包含 X 和 O。需要把所有不与边界连通的 O 填充成 X，水平或垂直相邻视为连通。

核心机制#

1. 扫描矩阵边界，对每个 O 执行 DFS。
2. DFS 把连通的安全区域标记为 #。
3. 扫描全矩阵：剩余 O 改为 X，# 恢复为 O。

Java 实现#

class Solution {
    public void solve(char[][] board) {
        if (board.length == 0 || board[0].length == 0) {
            return;
        }

        int rows = board.length;
        int columns = board[0].length;

        for (int row = 0; row < rows; row++) {
            markSafe(board, row, 0);
            markSafe(board, row, columns - 1);
        }
        for (int column = 0; column < columns; column++) {
            markSafe(board, 0, column);
            markSafe(board, rows - 1, column);
        }

        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                if (board[row][column] == 'O') {
                    board[row][column] = 'X';
                } else if (board[row][column] == '#') {
                    board[row][column] = 'O';
                }
            }
        }
    }

    private void markSafe(char[][] board, int row, int column) {
        if (
            row < 0 || row >= board.length ||
            column < 0 || column >= board[0].length ||
            board[row][column] != 'O'
        ) {
            return;
        }

        board[row][column] = '#';
        markSafe(board, row - 1, column);
        markSafe(board, row + 1, column);
        markSafe(board, row, column - 1);
        markSafe(board, row, column + 1);
    }
}

正确性与复杂度#

所有与边界连通的 O 都会从某个边界起点被访问并保留；没有被访问的 O 与边界不连通，按题意必然被包围。每个单元格最多处理常数次，时间复杂度为 O(mn)，递归栈最坏为 O(mn)。

验证#

覆盖全为 X、全为 O、单行矩阵、边界连通区域和完全封闭区域。

参考#

• LeetCode 130：被围绕的区域