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. }  

graph split （C++）

2维0，1矩阵。判断有多少个封闭的全是0的area。DFS，BFS的方法都要写。

void dfs(const vector<vector<int>> &G, int i, int j){
  if(i<0 || i >= rown || j<0 || j >= coln) return;
  if(G[i][j] == 1 || visited[i][j] == 1) return;
  visited[i][j] = 1;
  dfs(G, i - 1, j);
  dfs(G, i + 1, j);
  dfs(G, i, j+1);
  dfs(G, i, j-1);
}

int count(vector<vector<int>>G){
  if(G.empty()) return 0;
  int count;
 int rown = G.size(), coln = G[0].size;
 vector<vector<int>> visited(rown, vector<int>(coln,0));
  for(i = 0; i < rown; i++) {
    for(j = 0; j < coln; j++){
      if(visited[i][j] == 0&& G[i][j] == 0) {  
            count++;
          dfs(G,i, j, rown, coln);
        }
      }
    }

return count;

}

-------------------
void bfs(const vector<vector<int>> &G, int i, int j){
  queqe<pair<int,int>> q;
  q.push(make_pair(i,j));
  while(!q.empty()){
     i = queue.front().first; j = queue.front().second;
     queue.pop();
     visited[i][j] = 1;
     if(i > 0 && visited[i-1][j] == 0 && G[i-1][j] == 0) queue.push(make_pair(i-1,j));
     if(j> 0 && visited[i][j-1] == 0 && G[i][j-1] == 0) queue.push(make_pair(i,j-1));
     if(i < rown - 1 && visited[i+1][j] == 0 && G[i+1][j] == 0) queue.push(make_pair(i+1,j));
     if(j < coln - 1 && visited[i][j+1] == 0&& G[i][j+1] == 0) queue.push(make_pair(i,j+1));
  }
 

}


int count(vector<vector<int>>G){
  if(G.empty()) return 0;
  int count;
 int rown = G.size(), coln = G[0].size;
 vector<vector<int>> visited(rown, vector<int>(coln,0));
  for(i = 0; i < rown; i++) {
    for(j = 0; j < coln; j++){
      if(visited[i][j] == 0&& G[i][j] == 0) {  
            count++;
          bfs(G,i, j, rown, coln);
        }
      }
    }

return count;

}