题目链接：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
这道题的要求是将二维数组中被‘X’包围的‘O’全部变为‘X’（数组中只包含‘X’和‘O’）。
第一步，把周围一圈的‘O’及相连的‘O’都标记成没出现的字符，比如‘N’。第二步，把所有的‘O’变为‘X’，把所有的‘N’变为‘O’。
注意一点，在搜索的时候，不能递归进行深搜，这样会造成递归层数过深。
时间复杂度：O(mn)（m和n分别为board的长和宽）
空间复杂度：O(mn)（m和n分别为board的长和宽）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution
{
public:
void solve(vector<vector<char>> &board)
{
if(board.size() == 0 || board[0].size() == 0)
return;
// 将最上行和最下行的‘O’及其相连的‘O’改为‘N’
for(int j = 0; j < board[0].size(); ++ j)
{
if(board[0][j] == 'O')
search(board, 0, j);
if(board[board.size() - 1][j] == 'O')
search(board, board.size() - 1, j);
}
// 将最左列和最右列的‘O’及其相连的‘O’改为‘N’
for(int i = 0; i < board.size(); ++ i)
{
if(board[i][0] == 'O')
search(board, i, 0);
if(board[i][board[i].size() - 1] == 'O')
search(board, i, board[i].size() - 1);
}
// 把所有的‘N’变为‘O’，其他变为‘X’，
for(int i = 0; i < board.size(); ++ i)
for(int j = 0; j < board[0].size(); ++ j)
board[i][j] = board[i][j] == 'N' ? 'O' : 'X';
}
private:
void search(vector<vector<char>> &board, int x, int y)
{
int move[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
queue<vector<int>> q;
q.push({x, y});
board[x][y] = 'N';
while(!q.empty())
{
auto v = q.front();
q.pop();
// 沿上下左右四个方向进行搜索
for(int i = 0; i < 4; ++ i)
{
int xx = v[0] + move[i][0], yy = v[1] + move[i][1];
if(xx >=0 && xx < board.size() && yy >= 0 && yy < board[0].size()
&& board[xx][yy] == 'O')
{
q.push({xx, yy});
board[xx][yy] = 'N';
}
}
}
}
};