Surrounded Regions

lc130

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

For 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

解法1: 用bfs，dfs stackoverflow了，所以就是从边缘四周开始，只要是‘o'的就给标成keep，这样全部扫过一圈以后，只要将所有的k变成o，然后o编程x即可

class Node{
    int x;
    int y;

    public Node(int x, int y){
        this.x = x;
        this.y = y;
    }
}
public class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length == 0 || board[0] == null || board[0].length == 0) return ;
        for(int i = 0; i < board[0].length; i++){
            if(board[0][i] == 'O'){
                //board[0][i] = 'K';
                bfs(board, 0, i);
            }
        }
        for(int i = 0; i < board[0].length; i++){
            if(board[board.length - 1][i] == 'O'){
                //board[0][i] = 'K';
                bfs(board, board.length - 1, i);
            }
        }        


        for(int i = 0; i < board.length; i++){
            if(board[i][0] == 'O'){
                //board[0][i] = 'K';
                bfs(board, i, 0);
            }
        }

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

         for(int i = 0; i < board.length; i++){

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



    }
    public void bfs(char[][] board, int x, int y){
        if( x < 0 || x >= board.length || y < 0 || y >= board[0].length) return;
        Queue<Node> queue = new LinkedList<Node>();
        board[x][y] = 'K';
        queue.offer(new Node(x, y));
        while( !queue.isEmpty()){

            Node cur = queue.poll();
            int i = cur.x;
            int j = cur.y;
            //board[i][j] = 'K';           
            if(i - 1 >= 0 && board[i - 1][j ] == 'O' ){
                board[i - 1][j] = 'K';
                queue.offer(new Node(i - 1, j));
            }
            if(i + 1 < board.length  && board[i + 1][j ] == 'O' ){
                      board[i + 1 ][j] = 'K'; 
                queue.offer(new Node(i + 1, j));
            }
             if(j - 1 >= 0 && board[i ][j - 1] == 'O' ){
                      board[i ][j - 1] = 'K';
                queue.offer(new Node(i, j - 1));
            }
             if(j + 1 < board[0].length && board[i][j + 1 ] == 'O' ){
                       board[i][j + 1] = 'K';
                queue.offer(new Node(i, j + 1));
            }           
        }

    }

解法2: tle dfs

public class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length == 0 || board[0] == null || board[0].length == 0) return ;
        for(int i = 0; i < board[0].length; i++){
            if(board[0][i] == 'O'){
                //board[0][i] = 'K';
                dfs(board, 0, i);
            }
        }
        for(int i = 0; i < board[0].length; i++){
            if(board[board.length - 1][i] == 'O'){
                //board[0][i] = 'K';
                dfs(board, board.length - 1, i);
            }
        }        


        for(int i = 0; i < board.length; i++){
            if(board[i][0] == 'O'){
                //board[0][i] = 'K';
                dfs(board, i, 0);
            }
        }

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

         for(int i = 0; i < board.length; i++){

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



    }
    public void dfs(char[][] board, int x, int y){
        if( x < 0 || x >= board.length || y < 0 || y >= board[0].length) return;
        if(board[x][y] == 'O'){
            board[x][y] = 'K';
            dfs(board, x - 1, y);
            dfs(board, x + 1, y);            
            dfs(board, x, y + 1);
            dfs(board, x, y - 1);            
        }
    }
}