130. Surrounded Regions

We can search from 'O's on the board borders, and tag these 'O's as 'Y'. This can be done by DFS. Once these alive 'O's are tags, we can flip all remaining 'O's to 'X'. At the end, change all the alive 'O's (i.e. 'Y's) back to 'O'. Note, when doing DFS, we don't go back to check characters on borders.

1:  class Solution {  
2:  private:  
3:    int rows;  
4:    int cols;  
5:  public:  
6:    void solve(vector<vector<char>>& board) {  
7:      rows = board.size();  
8:      if (rows == 0) return;  
9:      cols = board[0].size();  
10:      for (int i = 0; i < rows; i++) {  
11:        check(board, i, 0);  
12:        if (cols > 1) check(board, i, cols-1);  
13:      }  
14:      for (int j = 1; j < cols-1; j++) {  
15:        check(board, 0, j);  
16:        if (rows > 1) check(board, rows-1, j);  
17:      }  
18:      for (int i = 0; i < rows; i++) {  
19:        for (int j = 0; j < cols; j++) {  
20:          if (board[i][j] == 'O') board[i][j] = 'X';  
21:        }  
22:      }  
23:      for (int i = 0; i < rows; i++) {  
24:        for (int j = 0; j < cols; j++) {  
25:          if (board[i][j] == 'Y') board[i][j] = 'O';  
26:        }  
27:      }  
28:    }  
29:    void check(vector<vector<char>> &board, int i, int j) {  
30:      if (board[i][j] == 'O') {  
31:        board[i][j] = 'Y';  
32:        if (i > 1) check(board, i-1, j);  
33:        if (i+1 < rows) check(board, i+1, j);  
34:        if (j > 1) check(board, i, j-1);  
35:        if (j+1 < cols) check(board, i, j+1);  
36:      }  
37:    }  
38:  };