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

 这道题一开始的思路是对的，就是先从边界dfs下去，这条路径上的O在最终都会保留，所以需要特殊标记一下，设为"Z“，”走“哈哈

出现在中间的O只要不能从边界到达的，都应该被改成X。

但是中间出现了一点小问题。一开始用递归总是出现runtime error。害我以为是访问越界了，看了下discussion才知道是stack overflow，正常。于是改用stack实现dfs就可以了。

经验总结：

runtime error 有可能是stack overflow 或者越界。

TLE有可能是出现了死循环。

1 class Solution { 2 public: 3     void solve(vector
     
      
       > &board) { 4         int m = board.size(); 5         if (m <= 1) return; 6         int n = board[0].size(); 7         if (n <= 1) return; 8          9         for (int i = 0; i < n; ++i) {10             if (board[0][i] == 'O') dfs(board, m, n, 0, i); 11         }12         for (int i = 0; i < n; ++i) {13             if (board[m - 1][i] == 'O') dfs(board, m, n, m - 1, i); 14         }15         for (int i = 1; i < m - 1; ++i) {16             if (board[i][0] == 'O') dfs(board, m, n, i, 0); 17         }18         for (int i = 1; i < m - 1; ++i) {19             if (board[i][n - 1] == 'O') dfs(board, m, n, i, n - 1); 20         }21         for (int i = 0; i < m; ++i) {22             for (int j = 0; j < n; ++j) {23                 if (board[i][j] == 'Z') {24                     board[i][j] = 'O';25                 } else if (board[i][j] == 'O') {26                     board[i][j] = 'X';27                 }28             }29         }30     }31 32     33     void dfs(vector
       
        
         > &board, int m, int n, int row, int col) {34         stack
         
           q;35         q.push(row * n + col);36         37         while (!q.empty()) {38             int pos = q.top();39             q.pop();40             int r = pos / n;41             int c = pos % n;42             board[r][c] = 'Z';43             if (r > 0 && board[r - 1][c] == 'O') q.push((r - 1) * n + c);44             if (r < m - 1 && board[r + 1][c] == 'O') q.push((r + 1) * n + c);45             if (c > 0 && board[r][c - 1] == 'O') q.push(r * n + c - 1);46             if (c < n - 1 && board[r][c + 1] == 'O') q.push(r * n + c + 1);47         }48     }49 };
         
        
       
      
     

 dfs递归就经常会有栈溢出的情况，所以涉及到遍历，能用bfs就用bfs。

涉及到bfs，就要考虑到是否会有重复添加到队列的情况。

1 class Solution { 2 public: 3     void solve(vector
     
      
       > &board) { 4         int m = board.size(); 5         if (m <= 1) return; 6         int n = board[0].size(); 7         if (n <= 1) return; 8          9         int x[] = {
   0, 0, 1, -1};10         int y[] = {-1, 1, 0, 0};11         for (int i = 0; i < n; ++i) {12             if (board[0][i] == 'O') bfs(board, x, y, 0, i);13             if (board[m - 1][i] == 'O') bfs(board, x, y, m - 1, i);14         }15         16         for (int i = 0; i < m; ++i) {17             if (board[i][0] == 'O') bfs(board, x, y, i, 0);18             if (board[i][n - 1] == 'O') bfs(board, x, y, i, n - 1);19         }20         21         for (int i = 0; i < m; ++i) {22             for (int j = 0; j < n; ++j) {23                 if (board[i][j] == 'O') board[i][j] = 'X';24                 if (board[i][j] == '$') board[i][j] = 'O';25             }26         }27     }28     29     void bfs(vector
       
        
         > &board, int x[], int y[], int row, int col) {30         queue
         
          
            > q;31 q.push(pair
           
            (row, col));32 board[row][col] = '$';33 int m = board.size();34 if (m <= 1) return;35 int n = board[0].size(), newRow, newCol;36 while (!q.empty()) {37 auto loc = q.front(); q.pop();38 39 for (int i = 0; i < 4; ++i) {40 newRow = loc.first + y[i]; 41 newCol = loc.second + x[i];42 if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && board[newRow][newCol] == 'O') {43 board[newRow][newCol] = '$';44 q.push(pair
            
             (newRow, newCol));45 }46 }47 }48 }49 };