poj 3026 Borg Maze(bfs+最小生成树）

题目：http://poj.org/problem?id=3026

题意真的很难懂。。。

题目大意：一个迷宫，'#'是墙，不可行走，‘ ‘是可行走的，现在题目是要求从s出发把所有的字母（‘A’）连起来的最短路径

各个字母的边权用bfs可求：墙不可走，超出矩阵范围不可走，建立任意字母之间最短距离的图

最后用prim就可以了

注：用getchar会wa，不知道为什么。。。

View Code

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #define inf 3000
  5 using namespace std;
  6 char map[105][105];//存储原始的迷宫
  7 int no[105][105];//记录字母的下标，map[i][j]是否为字母
  8 struct node
  9 {
 10     int x,y;
 11     int num;
 12 }que[2510];
 13 int nonde[4][2]={{0,-1},{0,1},{1,0},{-1,0}};//移动的方向
 14 int cmap[105][105];//存储各个字母之间的最短距离
 15 int n,m;
 16 int nnum;//字母的总数
 17 void bfs(int i,int j)
 18 {
 19     int vis[105][105];
 20     int head,tail;
 21     memset(vis,0,sizeof(vis));
 22     head=tail=0;
 23     que[head].x=i;
 24     que[head].y=j;
 25     que[head].num=0;
 26     vis[i][j]=1;
 27     tail++;
 28     while(head<tail)
 29     {
 30         if(no[que[head].x][que[head].y])
 31         {
 32             cmap[no[i][j]][no[que[head].x][que[head].y]]=que[head].num;//将此时的字母间的最短路径放入cmap
 33         }
 34         for(int k=0;k<4;k++)
 35         {
 36             int kx=que[head].x+nonde[k][0];
 37             int ky=que[head].y+nonde[k][1];
 38             if(kx>=1&&kx<=m&&ky>=1&&ky<=n)
 39             {
 40                 if(!vis[kx][ky]&&map[kx][ky-1]!='#')
 41                 {
 42                     que[tail].x=kx;
 43                     que[tail].y=ky;
 44                     que[tail].num=que[head].num+1;
 45                     vis[kx][ky]=1;
 46                     tail++;
 47                 }
 48             }
 49         }
 50         head++;
 51     }
 52     return ;
 53 }
 54 void prim()
 55 {
 56     int dis[105];
 57     int viss[105];
 58     int i,j;
 59     memset(viss,0,sizeof(viss));
 60     for(i=1;i<=nnum;i++)
 61     {
 62         dis[i]=cmap[1][i];
 63     }
 64     viss[1]=1;
 65     int min,pos;
 66     int ans=0;
 67     for(i=1;i<=nnum;i++)
 68     {
 69        min=inf;
 70        for(j=2;j<=nnum;j++)
 71        {
 72            if(!viss[j]&&min>dis[j])
 73            {
 74                pos=j;
 75                min=dis[j];
 76            }
 77        }
 78        if(min==inf)
 79        break;
 80        viss[pos]=1;
 81        ans+=min;
 82        for(j=2;j<=nnum;j++)
 83        {
 84            if(!viss[j]&&dis[j]>cmap[pos][j])
 85            dis[j]=cmap[pos][j];
 86        }
 87     }
 88     printf("%d\n",ans);
 89 }
 90 int main()
 91 {
 92     int t,i,j;
 93     scanf("%d",&t);
 94     while(t--)
 95     {
 96         scanf("%d%d",&n,&m);
 97         char temp[51];
 98         gets(temp);//用getchar()会wa
 99         memset(no,0,sizeof(no));
100         nnum=0;
101         for(i=1;i<=m;i++)
102         {
103             gets(map[i]);
104             for(j=0;j<n;j++)
105             {
106                 if(map[i][j]=='A'||map[i][j]=='S')
107                 {
108                     nnum++;
109                     no[i][j+1]=nnum;
110                 }
111             }
112         }
113         for(i=1;i<=m;i++)
114         {
115             for(j=1;j<=n;j++)
116             {
117                 if(no[i][j])
118                 bfs(i,j);//[i][j]到其他点的边权
119             }
120         }
121         prim();
122     }
123 
124     return 0;
125 }