POJ 3026 Borg Maze-白红宇

POJ 3026 Borg Maze

阅读量：7072 次

发布时间：2019-06-28

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

最小生成树+BFS

题意是说在迷宫之中找出连接全部点的最小生成树。其它杂项全然不理会。我理解题意就花了好久。

我用的Kruskal。输入的时候给每一个点标号。然后BFS 每一个点。找出近期的全部边，接下来就是模版的Kruskal。

由于是迷宫，所以仅仅能用BFS去搜与它相通的每一个点的最短路。

只是数据有点坑，建议数组开大一点，我提交的时候RE一次。绝对不止100个点。

然后输入完长宽之后。竟然还有莫名其妙的空格，所以不能getchar，直接gets一个吧，这让我WA了一次。

然后就下来就是AC了。。

。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define INF 0x7fffffff#define eps 1e-6using namespace std;int n,m,xl,yl;int cot;int xx[]= {-1,1,0,0};int yy[]= {0,0,-1,1};struct lx{ int u,v,len;} l[50*1001];int fa[1001];bool vis[151][151];char g[151][151];int site[151][151];struct node{ int x,y,lv;} point[1001];bool cmp(lx a,lx b){ return a.len
                 
                  q; q.push(S); vis[S.x][S.y]=1; int u=site[S.x][S.y]; int num=1; while(!q.empty()) { node now,tmp; tmp=q.front();q.pop(); int v=site[tmp.x][tmp.y]; if(v>=1&&u!=v) { l[cot].u=u; l[cot].v=v; l[cot++].len=tmp.lv; num++; } if(num==n)break; for(int k=0;k<4;k++) { int x=tmp.x+xx[k]; int y=tmp.y+yy[k]; if(y>=yl||y<0||x>=xl||x<0||g[x][y]=='#'||vis[x][y]) continue; vis[x][y]=1; now.lv=tmp.lv+1; now.x=x,now.y=y; q.push(now); } }}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%d",&xl,&yl); char str[51]; memset(site,0,sizeof(site)); n=1; gets(str); for(int i=0; i