算法

(DFS) $O(nm)$

本题是典型的泛洪填充$(flood\ fill)$，其实就是我们可以想象有一个洪水去淹没这个矩阵，如果遇见$X$就被阻隔在外不能淹没，如果遇见$O$就能一路顺着所有相连的$O$这样流淌下去，这时我们就会发现，所有被$X$完全包围的$O$，它是永远也不会被洪水淹没的，所有没有被$X$完全包围的$O$，也就是边界上的$O$，以及与边界上的$O$直接相连的其他所有的$O$都会被洪水淹没。所以本题就是让你找出不会被洪水淹没的$O$，然后维持$O$值不变，其他地方都把它置为$X$就可以了。

Java 代码

class Solution {
    public void solve(char[][] board) {
        int n = board.length;
        if (n == 0) return;
        int m = board[0].length;
        for (int i = 0; i < n; ++i) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][m - 1] == 'O') {
                dfs(board, i, m - 1);
            }
        }

        for (int j = 0; j < m; ++j) {
            if (board[0][j] == 'O') {
                dfs(board, 0, j);
            }
            if (board[n - 1][j] == 'O') {
                dfs(board, n - 1, j);
            }
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (board[i][j] == 'U') {
                    board[i][j] = 'O';
                }
                else board[i][j] = 'X';
            }
        }
    }

    public void dfs(char[][] board, int x, int y) {
        if (board[x][y] == 'X' || board[x][y] == 'U') return;
        board[x][y] = 'U';
        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};
        int n = board.length;
        int m = board[0].length;
        for (int i = 0; i < dx.length; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                dfs(board, nx, ny);
            }
        }
    }
}