题目描述

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

样例

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' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

算法分析

从外层出发，dfs深度遍历，将不被包围的'O'变成'#'，最后枚举整个二维数组，把'O'和'X'变成'X'，'#'变成'0'

时间复杂度 $O(n^2)$

Java 代码

class Solution {
    static int[] dx = new int[]{-1, 0, 1, 0};
    static int[] dy = new int[]{0, -1, 0, 1};
    static void dfs(char[][] board, int x,int y)
    {
        int n = board.length;
        int m = board[0].length;
        board[x][y] = '#';
        for(int i = 0;i < 4;i ++)
        {
            int a = x + dx[i];
            int b = y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(board[a][b] == 'O')
                dfs(board, a, b);
        }
    }
    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 i = 0;i < m;i ++)
        {
            if(board[0][i] == 'O') dfs(board, 0, i);
            if(board[n - 1][i] == 'O') dfs(board, n - 1, i);
        }

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