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
一刷：
- 在4条边上，如果有元素为'O', 则转为'1'， 并且与它相临的'O'都转为'1'
- 将其他的'O'都转为'X'
- 将'1'都转为'O'
public class Solution {
public void solve(char[][] board) {
int row = board.length;
if(row==0) return;
int col = board[0].length;
//flip the 0 in the edge and adjacent area to 1
for(int i=0; i<row; i++){
check(board, i, 0, row, col);//edge
if(col>1) check(board, i, col-1, row, col);//edge
}
for(int j=0; j<col; j++){
check(board, 0, j, row, col);//edge
if(row>1) check(board, row-1, j, row, col);//edge
}
//flip all other 0 to x
for(int i=0; i<row; i++){
for(int j=0; j<col; j++){
if(board[i][j] == 'O') board[i][j] = 'X';
}
}
//flip all 1 to 0
for(int i=0; i<row; i++){
for(int j=0; j<col; j++){
if(board[i][j] == '1') board[i][j] = 'O';
}
}
}
private void check(char[][] board, int i, int j, int row, int col){
//flip the 0 in the edge to 1
if(board[i][j] == 'O'){
board[i][j] = '1';
if(i>1) check(board, i-1, j, row, col);
if(j>1) check(board, i, j-1, row, col);
if(i+1<row) check(board, i+1, j, row, col);
if(j+1<col) check(board, i, j+1, row, col);
}
}
}
