【NC226 被围绕的区域】 DFS做法（java）

思路

用题目给的例子说明：

一开始是这样的矩阵：

[['X','X','X','X'],

['X','O','O','X'],

['X','O','X','X'],

['X','X','O','X']]

最外面那圈的'O'不会被围住，所以先把最外圈的'O'标记为'A'。

以及能从最外圈直接到达的'O'也标记为'A'。（这就要用到DFS）：

[['X','X','X','X'],

['X','O','O','X'],

['X','O','X','X'],

['X','X','A','X']]

再把中间区域被围绕的'O'变为'X'：

[['X','X','X','X'],

['X','X','X','X'],

['X','X','X','X'],

['X','X','A','X']]

最后再把'A'变回'O'：

[['X','X','X','X'],

['X','X','X','X'],

['X','X','X','X'],

['X','X','O','X']]

这就是要返回的矩阵了。

代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型二维数组 
     * @return char字符型二维数组
     */
    public char[][] surroundedArea (char[][] board) {
        // write code here
        int n=board.length;    // n行
        int m=board[0].length; // m列
        // 最外层的'O'先标记为'A'，能和最外层直接相连的'O'也标记为'A'
        for(int i=0;i<n;i++){
            dfs(board,i,0);  // 左边界
            dfs(board,i,m-1); // 右边界
        }
        for(int j=0;j<m;j++){
            dfs(board,0,j); // 上边界
            dfs(board,n-1,j); // 下边界
        }
        // 遍历整个矩阵，把'O'变为'X', 把'A'变为'O'
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(board[i][j]=='O')
                    board[i][j]='X';
                if(board[i][j]=='A')
                    board[i][j]='O';
            }
        }
        return board;
        
    }
    void dfs(char[][] board, int x, int y){
        // 不能超出边界
        // 注意最后一个条件不能写成board[x][y]=='X'，会进入死循环
        if(x<0||x>=board.length||y<0||y>=board[0].length||board[x][y]!='O')
            return;
        // 遇到O就改为A
        if(board[x][y]=='O')
            board[x][y]='A';  // 标记为A
        dfs(board,x-1,y);  //上
        dfs(board,x,y+1);  //右
        dfs(board,x+1,y);  //下
        dfs(board,x,y-1);  //左
    }
}