题目

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’是可以从外界走通的，保留 如果是’O’,说明这是闭塞的，从外界走不通的,替换为’X’。

代码

/**------------------------------------    *   日期：2015-02-06    *   作者：SJF0115    *   题目: 130.Surrounded Regions    *   网址：https://oj.leetcode.com/problems/surrounded-regions/    *   结果：AC    *   来源：LeetCode    *   博客：    ---------------------------------------**/    #include 
     
          #include 
      
           #include 
       
            #include 
        
             #include 
         
              using namespace std;    class Solution {    public:        void solve(vector
          
           
             > &board) { int row = board.size(); if(row == 0){ return; }//if int col = board[0].size(); // 都够不成围绕 if(row <= 2 || col <= 2){ return; }//if // 行 for(int i = 0;i < col;++i){ // 第一行 BFS(board,row,col,0,i); // 最后一行 BFS(board,row,col,row-1,i); }//for // 列 for(int j = 0;j < row;++j){ // 第一列 BFS(board,row,col,j,0); // 最后一列 BFS(board,row,col,j,col-1); }//for for(int i = 0;i < row;++i){ for(int j = 0;j < col;j++){ // 不可以从外界走通的o if(board[i][j] == 'O'){ board[i][j] = 'X'; }//if // 可以从外界走通的o else if(board[i][j] == '.'){ board[i][j] = 'O'; } }//for }//for } private: // row 行数 col 列数 x ,y 当前board位置 void BFS(vector
            
             
              > &board,int row,int col,int x,int y){ queue
              
               
                 > q; Pass(board,row,col,x,y,q); while(!q.empty()){ pair
                
                  point = q.front(); q.pop(); x = point.first; y = point.second; // left Pass(board,row,col,x,y+1,q); // right Pass(board,row,col,x,y-1,q); // up Pass(board,row,col,x-1,y,q); // down Pass(board,row,col,x+1,y,q); }//while } // 四边判断是否走通 void Pass(vector
                 
                  
                   > &board,int row,int col,int x,int y,queue
                   
                    
                      > &q){ // 边界条件以及遇到o才能走通 if(x < 0 || x >= row || y < 0 || y >= col || board[x][y] != 'O'){ return; }//if // 标记可从外界走通的o board[x][y] = '.'; // 入队列 q.push(make_pair(x,y)); } }; int main(){ Solution s; /*vector
                     
                      
                        > board = { {'X','X','X','X'}, {'X','O','O','X'}, {'X','X','O','X'}, {'X','O','X','X'} };*/ vector
                       
                        
                          > board = { { 'X','X','X'}, { 'X','O','X'}, { 'X','X','X'} }; s.solve(board); // 输出 for(int i = 0;i < board.size();i++){ for(int j = 0;j < board[i].size();j++){ cout<
                         
                          <<" "; }//for cout<
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

运行时间