# LeetCode | Surrounded Regions（包围的区域）

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```

``````//深度优先
class Solution {
public:
void solve(vector<vector<char>> &board) {
if(board.size() == 0 || board[0].size() == 0)
return ;
m = board.size();
n = board[0].size();
for(int i = 0;i < n;i++){
traverse(0,i,board);
traverse(m-1,i,board);
}
for(int i = 0;i < m;i++){
traverse(i,0,board);
traverse(i,n-1,board);
}
for(int i = 0;i < m;i++){
for(int j = 0;j < n;j++){
board[i][j] = board[i][j] == 'Z' ? 'O' : 'X';
}
}
}
//
void traverse(int x,int y,vector<vector<char>> &board){
if(x>=0 && x < m && y>=0 && y<n && board[x][y]=='O'){
board[x][y] = 'Z';      //将要保留的值赋一个额外的参数，更容易判断
traverse(x-1,y,board);  //有了入口条件，就随便上下左右递归，不用担心越界问题
traverse(x+1,y,board);
traverse(x,y-1,board);
traverse(x,y+1,board);
}
}
private:
int m,n;
};
``````

``````//广度优先
class Solution {
public:
void solve(vector<vector<char>> &board) {
if(board.size() == 0 || board[0].size() == 0)
return ;
m = board.size();
n = board[0].size();
for(int i = 0;i < n;i++){
if(board[0][i] == 'O')
traverse(0,i,board);
if(board[m-1][i] == 'O')
traverse(m-1,i,board);
}
for(int i = 0;i < m;i++){
if(board[i][0] == 'O')
traverse(i,0,board);
if(board[i][n-1] == 'O')
traverse(i,n-1,board);
}
for(int i = 0;i < m;i++){
for(int j = 0;j < n;j++){
board[i][j] = board[i][j] == 'Z' ? 'O' : 'X';
}
}
}

void add(int x,int y,vector<vector<char>> &board){
if(x>=0 && x < m && y>=0 && y<n && board[x][y]=='O'){
q.push(x*n+y);
board[x][y] = 'Z';
}
}

void traverse(int x,int y,vector<vector<char>> &board){
add(x,y,board);
while(!q.empty()){  //利用队列，来实现层序遍历
int p = q.front();
q.pop();
x = p/n;
y = p%n;
add(x-1,y,board);   //递归向栈中加入字符为‘O’的字符
add(x+1,y,board);
add(x,y-1,board);
add(x,y+1,board);
}

}
private:
queue<int> q;
int m,n;
};
``````