1 class Solution { 2 public: 3     /* 4      * @param board: board a 2D board containing 'X' and 'O' 5      * @return: nothing 6      */ 7     bool flag[220][220]; 8     vector
     
      
       > v; 9     const int dir[4][2] = {
   {
   0,1}, {
   1,0}, {
   0, -1}, {-1, 0}};10     int isChange = 1;11     void change_board(vector
       
        
         > &board){12         for(size_t i = 0; i < v.size(); ++i){13                 int x = v[i].first;14                 int y = v[i].second;15                 board[x][y] = 'X';16         }17     }18     void surroundedRegions(vector
         
          
           > &board) {19 // write your code here20 memset(flag, 0, sizeof(flag));21 for(size_t i = 0; i < board.size(); ++i){22 for(size_t j = 0; j < board[i].size(); ++j){23 if(flag[i][j] == 0 && board[i][j] == 'O'){24 v.push_back(make_pair(i,j));25 bfs(i,j, board);26 if(isChange == 1){27 //printf("change:%d %d\n",i,j);28 change_board(board);29 }30 v.clear();31 isChange = 1;32 }33 }34 }35 }36 void bfs(int x, int y, vector
           
            
             > board){37 queue
             
              
               > que;38 que.push(make_pair(x,y));39 flag[x][y] = 1;40 while(!que.empty()){41 pair
               
                 p = que.front();42 que.pop();43 44 45 46 int nx = 0, ny = 0;47 for(int i = 0; i < 4; ++i){48 nx = p.first + dir[i][0];49 ny = p.second + dir[i][1];50 if(nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size()){51 if(flag[nx][ny] == 0 && board[nx][ny] == 'O'){52 v.push_back(make_pair(nx, ny));53 que.push(make_pair(nx, ny));54 flag[nx][ny] = 1;55 }56 } else {57 // printf("dsad:%d %d\n",nx, ny);58 isChange = 0;59 }60 61 }62 }63 }64 };
               
              
             
            
           
          
         
        
       
      
     

dfs会爆栈 可以 bfs或者用栈模拟函数