算法练习-被围绕的区域

题目描述

题目描述：
给定一个二维的矩阵，包含 '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'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/surrounded-regions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

从题目的理解看，边界上的O 没有被X包围，不能变X，同样与边界的O相连的O也是被看做没有被X包围，因此也不能变成X。因此我们可以得出这样的结论，凡是边界的O，以及相连的O都不能变X，其余的O变X。
所以我们可以对边界上的O进行深度遍历或是广度遍历，把这些O用另外的符号代替（这里我用A代替），然后再遍历整个矩阵，把A的元素改为O，其余的改为X。

代码

//code
class Solution {
    int n,m;
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        n = board.length;
        m = board[0].length;

        // 对上下边界的'O'进行深度遍历
        for(int i =0;i<m;i++){
            dfs(board,0,i);
            dfs(board,n-1,i);
        }

        // 对左右边界的'O'进行深度遍历
        for(int i =0;i<n;i++){
            dfs(board,i,0);
            dfs(board,i,m-1);
        }

        //对标记的A的修改为‘O’，其余改为‘X’
        for(int i =0;i<n;i++){
            for(int j = 0;j<m;j++){
               if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }

    }

   public void dfs(char[][] board,int x,int y){
        //当遍历的元素超出边界范围或是当前遍历元素不是“O”，就不用进行深度遍历了
        if(x<0||x>=n||y<0||y>=m||board[x][y]!='O'|| board[x][y] == 'A'){
            return; 
        }  
        board[x][y] = 'A';
        dfs(board,x+1,y);
        dfs(board,x-1,y);
        dfs(board,x,y+1);
        dfs(board,x,y-1);
    }
}