130. 被围绕的区域（DFS）

130. 被围绕的区域

• 题目
• 解题思路
• 代码

题目

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

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

解题思路

可达性问题，用DFS。
这题主要思路你要想到 从四条边开始往内排除。而不是从内往外寻找。

• 题目要求在边界的字母’O’都不会被填充，被X包围的才会被填充。
• 那么我们可以把二维数组想象成一个正方形， 我们先从四条边找出不会被填充的。也就是四条边上的’O’。
• 但是注意，与四条边上的’O’相连的’O’也不会被填充，因为既然和边界上的”O“相连了，那么这些”O“必不可能被包围，因为边界那个”O“是一定不会被包围住的。
  • 所以我们只需要做三步：
    ①找到边界的所有"O"，以及和它们直接或间接相连的“O”，将它们替换成*
    ②遍历二维数组，找到剩下的“O” 用”X”进行填充
    ③把*恢复成“O”

代码

class Solution {
        public void solve(char[][] board) {
        if (board.length <= 0 || board[0].length <= 0) {//保证数组不为空
            return;
        }
        int r = board.length;
        int c = board[0].length;

        for (int i = 0; i < r; i++) {//遍历所有行的第一列和最后一列
            if (board[i][0] == 'O') {
                DFS(board, i, 0);//所有行的第一列
            }
            if (board[i][c - 1] == 'O') {
                DFS(board, i, c - 1);//所有行的最后一列
            }
        }

        for (int i = 0; i < c; i++) {//遍历所有列的第一行和最后一行
            if (board[0][i] == 'O') {
                DFS(board, 0, i);//所有列的第一行
            }
            if (board[r - 1][i] == 'O') {
                DFS(board, r - 1, i);//所有列的最后一行
            }
        }

            /*经过上面两个步骤已经把四边上的'O',和与其相连的'O'都给变成'*'了，接下来
            只要遍历整个数组，将剩下来的'O'变成'X'然后把'*'恢复成'O' */
        for (r = 0; r < board.length; r++) {
            for (c = 0; c < board[0].length; c++) {
                if (board[r][c] == 'O') {
                    board[r][c] = 'X';
                }
                if (board[r][c] == '*') {
                    board[r][c] = 'O';
                }
            }
        }

    }

    public void DFS(char[][] board, int r, int c) {
        if (r < 0 || r > board.length || c < 0 || c > board[0].length) {//如果越界了
            return;
        }
        if (board[r][c] == 'O') {
            board[r][c] = '*';//将'O'变成'*'
        }

        //从四个方向顺找和'O'相连的'O'
        if (r < board.length - 2 && board[r + 1][c] == 'O') {
            //因为最后一行是边界。在最开始就找过了所以r < board.length - 2。如果没越界还要保证将要找的这个是'O',如果不是"O"就没必要找了
            DFS(board, r + 1, c);//下
        }
        if (r > 1 && board[r - 1][c] == 'O') {
            //往上找的话第一行是边界，所以不能到第一行，即r > 1
            DFS(board, r - 1, c);//上
        }
        if (c < board[0].length - 2 && board[r][c + 1] == 'O') {
            //往右找的话。最后一列是边界，已经找过了。所以c < board[0].length - 2
            DFS(board, r, c + 1);//右
        }
        if (c > 1 && board[r][c - 1] == 'O') {
            //往左找的话第一行是边列，所以不能到第一列，即c > 1
            DFS(board, r, c - 1);//左
        }


    }
}