[C++知识库]矩阵dfs(130. 被围绕的区域)

20210904矩阵深度优先搜索

130. 被围绕的区域

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在边界并且与其相连的O就视为“突围”，被包围就变成X

? 难点在于如何确定O是不是连续的，那我们反其道而行之，去找不连续的“O”.用“o”表示他是不连续的。之后再进行遍历，如果为“O”那么就置为“X”，如果是“o”(不连续的)那么还原为“O”；

深度优先遍历

class Solution {

    char[][] board;

    //方向数组
    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,1,-1};

    int m;
    int n;

    public void solve(char[][] board) {
        //边界条件:空矩阵的情况
        if(board==null||board.length ==0)return;
        
        //成员变量赋值
        this.m = board.length;
        this.n = board[0].length;
        this.board = board;

        //首先找到所有"O",连续的话不操作,如果不连续标记为"o",标记操作在dfs中进行

        //和围棋相同 边界上的O不会被吃掉,与边界"O"相连的不会被吃掉

        //对第一列和最后一列的O进行dfs,并且把边界相连的O标记

        for(int i=0;i < m;i++){
            dfs(i,0);
            dfs(i,n-1);
        }
        //对第一列和最后一列的所有Odfs
        for(int i=0;i < n;i++){
            dfs(0,i);
            dfs(m-1,i);
        }

        //遍历矩阵如果'o'->'O' 如果 'O'->'X'
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(board[i][j]=='O') board[i][j]='X';

                if(board[i][j]=='o') board[i][j]='O';
            }

        }



    }

    public void dfs(int x,int y){
        //边界条件: 越界和"x"就返回;
        
        if(x<0||x >= m||y<0||y>=n||board[x][y]!='O') return;


        //如果等于O就标记
        board[x][y] = 'o';

        for(int i = 0;i<4;i++){

            dfs(x+dx[i],y+dy[i]);

        }
 
    }
}