LeetCode--Surrounded Regions

 1 class Solution {
 2 public:
 3     void solve(vector<vector<char>> &board) {
 4         int m = board.size();
 5         if(m == 0)
 6             return;
 7         int n = board[0].size();
 8         int i,j;
 9         for(i=0;i<m;i++)  
10         {  
11             if (board[i][0]=='O')  
12                 bfs(i,0,board);  
13             if (board[i][n-1]=='O')  
14                 bfs(i,n-1,board);  
15         }  
16         for(j=0;j<n;j++)  
17         {  
18             if (board[0][j]=='O')  
19                 bfs(0,j,board);  
20             if (board[m-1][j]=='O')  
21                 bfs(m-1,j,board);  
22         }  
23         for(i=0;i<m;i++)  
24         {
25             for(j=0;j<n;j++)  
26             {  
27                 if(board[i][j]=='O')  
28                     board[i][j]='X';  
29                 else if (board[i][j]=='E')  
30                     board[i][j]='O';  
31             }  
32         }
33     }
34     void bfs(int i,int j,vector<vector<char>> &board){
35         int m = board.size();
36         int n = board[0].size();
37         
38         queue<pair<int,int> > Q;
39         Q.push(make_pair(i,j));
40         board[i][j] = 'E';
41         int dx[4] = {-1,0,0,1};
42         int dy[4] = {0,-1,1,0};
43         while(!Q.empty()){
44             pair<int,int> p = Q.front();
45             Q.pop();
46             
47             int iidx = p.first;
48             int jidx = p.second;
49             
50             for(int i = 0 ; i < 4 ; ++i){
51                 int itmp = iidx+dx[i];
52                 int jtmp = jidx+dy[i];
53                 
54                 if((itmp < m && itmp >= 0)&&(jtmp < n && jtmp >= 0) && board[itmp][jtmp] == 'O'){
55                     Q.push(make_pair(itmp,jtmp));
56                     board[itmp][jtmp] = 'E';
57                 }
58             }
59         }
60     }
61 };
dfs和bfs都可以