130. 被围绕的区域

上帝关上了你的一扇门，必然在别处为你打开了一扇窗。

参考130. 被围绕的区域。

题目

给你一个 m x n 的矩阵 board ，由若干字符 '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' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
输入：board = [["X"]]
输出：[["X"]]

解题思路

• 深度优先搜索：递归dfs搜索边缘O和间接相邻边缘O的字符进行标记,最后恢复标记。

深度优先搜索

class Solution {

    char[][] b;
    int m,n;
    public void solve(char[][] board) {
        b = board;
        m = b.length;
        n = b[0].length;
        //边缘的`O` 递归找间接与它相连的`O`
        // for(int i = 0; i < m;i++) {
        //     for(int j = 0; j < n; j++) {
        //         if(b[i][j] == 'O' &&(i==0||j==0||i==m-1||j==n-1)) dfs(i,j);
        //     }
        // }
        //优化判断边缘'O'
        if(m == 0||n == 0) return;
        for(int i = 0; i < m;i++) {
            if(b[i][0] == 'O') dfs(i,0);
            if(b[i][n-1] == 'O') dfs(i,n-1);
        }
        for(int j = 0; j < n; j++) {
            if(b[0][j] == 'O') dfs(0,j);
            if(b[m-1][j] == 'O') dfs(m-1,j);
        }
        //恢复边缘`O`
        for(int i = 0; i < m;i++) {
            for(int j = 0; j < n; j++) {
                if(b[i][j] == 'O') b[i][j] = 'X';
                else if(b[i][j] == 'Y') b[i][j] = 'O';
            }
        }
    }

    void dfs(int i,int j) {
        b[i][j] = 'Y';
        if(i+1 < m && b[i+1][j] == 'O') dfs(i+1,j);
        if(i-1 >= 0 && b[i-1][j] == 'O') dfs(i-1,j);
        if(j+1 < n && b[i][j+1] == 'O') dfs(i,j+1);
        if(j-1 >= 0 && b[i][j-1] == 'O') dfs(i,j-1);
    }
}

复杂度分析

• 时间复杂度：O(mn)，m/n为矩阵的行数和列数,dfs中每一个字符最多会被标记一次。
• 空间复杂度：O(mn)，主要为深度优先搜索的栈的开销。