Given a 2D board containing 'X' and '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
public class Solution { public void solve(char[][] board) { // Start typing your Java solution below // DO NOT write main() function if(board == null || board.length == 0) return; int row = board.length-1; int col = board[0].length -1; for(int i = 0 ; i <= row; i ++){ if(board[i][0] == 'O') //first line dfs(board,i,0); if(board[i][col] == 'O')// bottom line dfs(board,i,col); } for(int j = 1 ; j < col; j++){ if(board[0][j] == 'O') dfs(board,0,j); if(board[row][j] == 'O') dfs(board,row,j); } for(int i = 0 ; i <= row ; i++){ for(int j = 0 ; j <= col ; j++){ if(board[i][j] == 'O') {board[i][j] = 'X';} else if(board[i][j] == '+'){ board[i][j] = 'O'; } } } } public void dfs(char[][] board, int x, int y){ board[x][y] = '+'; if(x-1 > 0 && board[x-1][y] == 'O') dfs(board,x-1,y); if(y-1 >=0 && board[x][y-1] =='O') dfs(board,x,y-1); if(x+1 < board.length && board[x+1][y] == 'O') dfs(board,x+1,y); if(y+1 < board[0].length && board[x][y+1] == 'O') dfs(board,x,y+1); } }