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

bfs/dfs.

public class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length == 0|| board[0].length==0) return;
        class Node{
            int x;
            int y;
            Node(int i, int j){
                x = i;
                y = j;
            }
        }

        ArrayList<Node> queue = new ArrayList<>();

        int m = board.length;
        int n = board[0].length;
        for(int i=0; i< m; i++){
            if(board[i][0] == 'O'){
                queue.add(new Node(i,0));
            }
            if(board[i][n-1] == 'O'){
                queue.add(new Node(i, n-1));
            }
        }
        for(int i=1; i<n-1; i++){
            if(board[0][i] == 'O') queue.add(new Node(0, i));
            if(board[m-1][i] == 'O') queue.add(new Node(m-1, i));
        }

        int k =0;
        while(k < queue.size()){
            Node node = queue.get(k);
            int x = node.x;
            int y = node.y;

            board[node.x][node.y] = 'U';
            k++;
            if(x > 0 && board[x-1][y] == 'O'){
                queue.add(new Node(x-1,y));
            }
            if(x<m-1 && board[x+1][y] == 'O'){
                queue.add(new Node(x+1, y));
            }
            if(y >0 && board[x][y-1] == 'O'){
                queue.add(new Node(x, y-1));
            } 
            if(y < n-1 && board[x][y+1] == 'O'){
                queue.add(new Node(x, y+1));
            }
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == 'U') board[i][j] = 'O';
            }
        }
    }
}

Or you can get a recursive solution. which go ove the border of the board, if find a 'O', then dfs from this point. mark itself and its neighbor as 'U' recursively.

results matching ""

    No results matching ""