leetcode Surrounded Regions 详解 - c++编程基础

其实这道题非常思路简单，bfs或者dfs找到所有连在一起的O，如果这些O中有一个挨着边，那就不变，否则就是被surrounded的，全部变成X就行

但是很久没写bfs导致了入队的时候没有判重，导致了大量的点入队超过1次。所以Large dataset时就TLE了。判重之后轻松通过，64ms。不多说了，直接上代码：

 
/** 
 * @file Surrounded_Regions.cpp 
 * @Brief  
 * @author  Brian  
 * @version 1.0 
 * @date 2013-09-07 
 */  
  
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
using namespace std;  
   
  
class Solution {  
    private:   
        struct point{  
            int x;  
            int y;  
            point(int _x,int _y):x(_x),y(_y){}  
            point(){}  
        };  
        int start;  
        int end;  
        point Points[100000];  
        void bfs(vector > &board, int r,int c, int row, int col){  
            vector buf;  
            queue q;  
            bool reachBoundary = false;  
            start = 0;  
            end =0;  
            //q.push(point(r,c));  
            Points[end++]=point(r,c);  
            //while(!q.empty()){  
            while(start > &board , queue &q, int x,int y, int row, int col,char c){  
            if(x<0||x>




=row||y<0||y>=col)  
                return true;  
            else{  
                if(board[x][y]==c ){  
                    //q.push(point(x,y));  
                    Points[end++]=point(x,y);  
                    //这个是判重用的，防止同一个点入队多次。下一次到这一个点时  
                    // if判断就不成立了,也就防止了再次入队。  
                    board[x][y]=c+1;  
                       
                }  
                return false;  
            }  
        }  
    public:  
        Solution(){  
  
        }  
        void solve(vector > &board) {  
  
            int row = board.size();  
            if(row==0)  
                return ;  
            int col = board[0].size();  
            for(int r=0;r > board;  
    int n=20;  
    for(int i=0;i row;  
        for(int j=0;j