June Leetcoding Challenge(6.17)

LeetCode六月挑战（6.17） Surrounded Regions LeetCode130 解题报告

Surrounded Regions

Solution
Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

Example:

X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X
Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

思路

使用DFS搜索O，首先判断O是否在边界，如果在边界并且他的值为O的时候，开始DFS。搜索四个边界里为O的坐标，并将它们设置成G。DFS结束后，开始循环，将为O的地方变为X，将为G的地方变为O即可。

代码

class Solution {
    public void solve(char[][] board) {
        int n = board.length;
        if(n==0)
            return;
        int m = board[0].length;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                boolean flag = i==0||j==0||i==n-1||j==m-1;
                if(flag && board[i][j]=='O')
                    dfs(board,i,j);
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(board[i][j]=='O') 
                    board[i][j] = 'X';
                else if(board[i][j]=='G') board[i][j] = 'O';
            }
        }
    }
    
    public static void dfs(char[][] board,int x, int y){
        int n = board.length;
        int m = board[0].length;
        if(x<0||x==n||y<0||y ==m||board[x][y]!='O')
            return;   
        board[x][y]='G';
        dfs(board,x,y-1);
        dfs(board,x-1,y);
        dfs(board,x+1,y);
        dfs(board,x,y+1);
    }
}