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.
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
给定一个矩形，若"O"节点被"X"节点包围，则这些"O"节点转换为"X"。类似于围棋。
若"O"节点不想被包围，则边框处至少有一个"O"节点通向矩阵外，否则则被完全包围。因此先从边框处找"O"节点，顺势向里找，则为不被吞掉的"O"节点群。
首先检验边框节点，若边框节点为"O"，则检验该节点四周节点，若同样为"O"，则将这些"O"赋值为"1"，bfs。
检验完全后，将变换后的矩形中剩余的"O"改为"X"，因为这些"O"没有通向矩阵边缘，属于被吞噬的节点。再将变换为"1"的未被吞噬的节点改回"O"。
class Solution {
public:
void solve(vector<vector<char>>& board) {
if(board.size()==0) return;
int row = board.size();
int col = board[0].size();
for(int i=0; i<row; i++){
check(board, i, 0, row, col);
if(col>1){
check(board, i, col-1, row, col);
}
}
for(int j=0; j<col; j++){
check(board, 0, j, row, col);
if(row>1){
check(board, row-1, j, row, col);
}
}
for(int i=0; i<row; i++){
for(int j=0; j<col; j++){
if(board[i][j] == 'O') board[i][j] = 'X';
if(board[i][j] == '1') board[i][j] = 'O';
}
}
}
void check(vector<vector<char>>& vec, int i, int j, int row, int col){
if(vec[i][j] == 'O'){
vec[i][j] = '1';
if((i-1)>=0){
check(vec, i-1, j, row, col);
}
if((i+1)<row){
check(vec, i+1, j, row, col);
}
if((j-1)>=0){
check(vec, i, j-1, row, col);
}
if((j+1)<col){
check(vec, i, j+1, row, col);
}
}
}
};
