130. 被围绕的区域

题目描述

给定一个二维的矩阵，包含 '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

思路

1. 使用深度优先搜索算法
2. 从四个位置开始进行DFS：

• 第一行
• 最后一行
• 第一列
• 最后一列

3.DFS完成后，将标识位为false对应的位置设置成“X”即可。

Java代码实现

    public void solve(char[][] board) {
        if(board.length == 0)
            return;
        boolean[][] flags = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            if(board[i][0] == 'O')
                solveDfs(flags,board,i,0);
            if(board[i][board[0].length-1] == 'O')
                solveDfs(flags,board,i,board[0].length-1);
        }

        for (int i = 0; i < board[0].length; i++) {
            if(board[0][i] == 'O')
                solveDfs(flags,board,0,i);
            if(board[board.length-1][i] == 'O')
                solveDfs(flags,board,board.length-1,i);
        }

        for (int i = 0; i < flags.length; i++) {
            for (int j = 0; j < flags[0].length; j++) {
                if(!flags[i][j])
                    board[i][j] = 'X';
            }
        }
    }

    private void solveDfs(boolean[][] flags,char[][] chars,int i,int j){
        if(i<0 || j<0 || i >=flags.length || j >= flags[0].length)
            return;
        if(flags[i][j])
            return;
        if(chars[i][j] == 'O'){
            flags[i][j] = true;
            //左
            solveDfs(flags,chars,i,j-1);
            //上
            solveDfs(flags,chars,i-1,j);
            //右
            solveDfs(flags,chars,i,j+1);
            //下
            solveDfs(flags,chars,i+1,j);
        }
    }