Surrounded regions(C++ code)

Leetcode Surrounded Regions, Feb 22
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不动，被围在里面的O变为X。这里有个trick，就是先把边界相连的O变为另一个符号#，然后遍历矩阵，把#变回O，同时把O变为X，就可以了。找所有的边界O需要用到dfs，只对所有边界元素遍历，这里的特殊之处在于遇到X或者#都直接返回，只有遇到O才加以处理并继续DFS，因此不需要另外使用map判定条件了。

0. #depth-first-search and change boundary O's to #'s.  
1. void dfs(vector<vector<char>> &board, int i, int j){  
2.   
3.   if(board[i][j] == 'X' || board[i][j] == '#') return;  
4.   
5.   board[i][j] = '#';   
6.   
7.   if(i > 0) dfs(board,i-1,j);  
8.   
9.   if(i < board.size()-1) dfs(board,i+1,j);  
10.   
11.   if(j > 0) dfs(board,i,j-1);  
12.   
13.   if(j < board[0].size() - 1) dfs(board,i,j+1);  
14.   
15. }   
16.   
17.    
18.   
19. void solve(vector<vector<char>> &board) {  
20.   
21.         if(board.empty()) return;  
22.  
23.         #r is row number, c is column numer  
24.         int r = board.size(), c = board[0].size();  
25.  
26.         #do dfs on the boundary lines  
27.         for(int i = 0; i < c; i++){  
28.   
29.           dfs(board,0,i);  
30.   
31.           dfs(board,r-1,i);   
32.   
33.         }   
34.   
35.         for(int j = 1; j < r-1; j++){  
36.   
37.           dfs(board,j,0);  
38.   
39.           dfs(board,j,c-1);   
40.   
41.         }   
42.        
43.         #change #'s back to O's, change O's to X's  
44.         for(int i = 0; i < r; i++){  
45.   
46.            for(int j = 0; j < c; j++){  
47.   
48.              if(board[i][j] == '#') board[i][j] = 'O';  
49.   
50.              else if(board[i][j] == 'O') board[i][j] = 'X';   
51.            }  
52.         }  
53. }