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.