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

思路：

类似以前写的迷宫类题目，递归实现，但是调试的过程中还是费了些功夫，头脑不够清晰。

通过观察如果O区域有一块在边缘，那么就不会变成X，其余的O区域都会变成X。所以直接从四条边上的O开始扩散，用另一个vector记录是否有扩散到，最后根据那个vector的结果重新给原board赋值即可。

 1     vector<vector<bool> > v;
 2     int m,n;
 3     void visit(int row, int col, vector<vector<char> > &board){      
 4         if(row < 0 || row > m-1 || col < 0 || col > n-1)
 5             return;
 6         if(board[row][col] == 'X')
 7             return;
 8         v[row][col] = true;
 9         board[row][col] = 'X';
10         visit(row+1, col, board);
11         visit(row-1, col, board);
12         visit(row, col+1, board);
13         visit(row, col-1, board);
14     }
15     void solve(vector<vector<char> > &board) {
16         // IMPORTANT: Please reset any member data you declared, as
17         // the same Solution instance will be reused for each test case.
18         m = board.size();
19         if(m == 0)
20             return;
21         n = board[0].size();
22         if(n == 0)
23             return;
24         v = vector<vector<bool> >(m,vector<bool>(n,false));
25         int i,j;
26         for(i = 0; i < n; i++){
27             if(board[0][i] == 'O')
28                 visit(0, i, board);
29         }
30         for(i = 0; i < n; i++){
31             if(board[m-1][i] == 'O')
32                 visit(m-1, i, board);
33         }
34         for(i = 0; i < m; i++){
35             if(board[i][0] == 'O')
36                 visit(i, 0, board);
37         }
38         for(i = 0; i < m; i++){
39             if(board[i][n-1] == 'O')
40                 visit(i, n-1, board);
41         }
42         for(i = 0; i < m; i++){
43             for(j = 0; j < n; j++){
44                 board[i][j] = v[i][j] ? 'O':'X';
45             }
46         }
47     }

第二遍。原先的代码发现不能AC了，可能是数据变大了，栈溢出，所以改成宽搜。

 1     void visit(int x, int y, vector<vector<char> > &board, vector<vector<int> > &maze){
 2         int m = board.size(), n = board[0].size();
 3         queue<pair<int, int> > Queue;
 4         Queue.push(pair<int, int>(x,y));
 5         while(!Queue.empty()){
 6             pair<int, int> tmp = Queue.front();
 7             Queue.pop();
 8             int i = tmp.first;
 9             int j = tmp.second;
10             if(i < 0 || j < 0 || i >= m || j >= n)
11                 continue;
12             if(board[i][j] == 'X' || maze[i][j])
13                 continue;
14             maze[i][j] = 1;
15             Queue.push(pair<int, int>(i+1, j));
16             Queue.push(pair<int, int>(i-1, j));
17             Queue.push(pair<int, int>(i, j+1));
18             Queue.push(pair<int, int>(i, j-1));
19         }
20     }
21     void solve(vector<vector<char> > &board) {
22         // IMPORTANT: Please reset any member data you declared, as
23         // the same Solution instance will be reused for each test case.
24         int m = board.size();
25         if(m == 0)
26             return;
27         int n = board[0].size();
28         vector<vector<int> > maze(m, vector<int>(n, 0));
29         int i,j;
30         for(i = 0; i < n; i++){
31             if(board[0][i] == 'O' && maze[0][i] == 0)
32                 visit(0, i, board, maze);
33             if(board[m-1][i] == 'O' && maze[m-1][i] == 0)
34                 visit(m-1, i, board, maze);
35         }
36         for(i = 0; i < m; i++){
37             if(board[i][0] == 'O' && maze[i][0] == 0)
38                 visit(i, 0, board, maze);
39             if(board[i][n-1] == 'O' && maze[i][n-1] == 0)
40                 visit(i, n-1, board, maze);
41         }
42         for(i = 0; i < m; i++){
43             for(j = 0; j < n; j++){
44                 if(!maze[i][j])
45                     board[i][j] = 'X';
46             }
47         }
48     }