【BFS】【map】hdu5925 Coconuts-白红宇

【BFS】【map】hdu5925 Coconuts

阅读量：6080 次

发布时间：2019-06-20

本文共 1672 字，大约阅读时间需要 5 分钟。

题意：一张n*m的网格图（n和m可以达到10^9），其中K个点是障碍物（不超过200个），问你没有被障碍物占据的点形成了几个连通块？并且输出各个连通块的大小。

容易证明，大小超过40000的连通块最多只有一个。于是可以从每个与障碍物邻接的非障碍点出发bfs，限制步数不超过40000，这样就可以找到所有小的连通块。最后如果n*m-K-小的连通块的总大小不等于0，则剩下的就是那个大的连通块的大小。

用map打标记进行判重。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           using namespace std;typedef long long ll;typedef pair
           
             Point;const int dx[]={0,-1,0,1,1,-1,1,-1},dy[]={-1,0,1,0,-1,-1,1,1};const int dx1[]={0,-1,0,1},dy1[]={-1,0,1,0};Point p[205];int T,m,n,K;int main(){ scanf("%d",&T); for(int zu=1;zu<=T;++zu){ map
            
             vis; set
             
              za; vector
              
               vs; printf("Case #%d:\n",zu); scanf("%d%d%d",&n,&m,&K); for(int i=1;i<=K;++i){ scanf("%d%d",&p[i].first,&p[i].second); za.insert(p[i]); } int bj=0; for(int i=1;i<=K;++i){ int x=p[i].first,y=p[i].second; for(int j=0;j<8;++j){ int tx=x+dx[j],ty=y+dy[j]; if(tx>=1 && tx<=n && ty>=1 && ty<=m){ if(za.find(Point(tx,ty))==za.end()){ if(!vis[Point(tx,ty)]){ ++bj; queue
               
                q; q.push(Point(tx,ty)); vis[Point(tx,ty)]=bj; int cnt=1; bool flag=1; while(!q.empty()){ Point U=q.front(); q.pop(); for(int k=0;k<4;++k){ int ttx=U.first+dx1[k],tty=U.second+dy1[k]; if(ttx>=1 && ttx<=n && tty>=1 && tty<=m && za.find(Point(ttx,tty))==za.end()){ int tmp=vis[Point(ttx,tty)]; if(tmp>0 && tmp
                
                 40000){ flag=0; goto OUT; } } } } } OUT: if(flag){ vs.push_back((ll)cnt); } } } } } } ll sum=0; for(vector
                 
                  ::iterator it=vs.begin();it!=vs.end();++it){ sum+=(*it); } if((ll)n*(ll)m>sum+(ll)K){ vs.push_back((ll)n*(ll)m-sum-(ll)K); } sort(vs.begin(),vs.end()); int sz=vs.size(); printf("%d\n",sz); for(int i=0;i

转载于:https://www.cnblogs.com/autsky-jadek/p/7885600.html

你可能感兴趣的文章

玩转搭载眼球追踪的FOVE 0，需要多高的配置呢？