poj 3026 Borg Maze(bfs+prim)

  1 /*注意：G++递交AC，C++递交编译错误  Compile Error*/
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstdlib>
  5 #include <cstring>
  6 #include <queue>
  7 using namespace std;
  8 const int MAX=150;
  9 const int INF=0xfffffff;
 10 char g[MAX][MAX];  //存放地图
 11 int egde[MAX][MAX]; //字母间的最短距离
 12 int vis[MAX][MAX],num[MAX][MAX];//vis广搜用的标记数组，num给字母编号
 13 int dis[MAX][MAX];  
 14 int t,x,y,cnt,nc;
 15 int dirx[]= {0,0,1,-1}; //四个方向的坐标
 16 int diry[]= {1,-1,0,0};
 17 struct Pos
 18 {
 19     int x;
 20     int y;
 21 };
 22 void fun()  //给字母编号
 23 {
 24     nc=0;  // 字母个数
 25     memset(num,-1,sizeof(num));
 26     for(int i=0; i<y; i++)
 27     {
 28         for(int j=0; j<x; j++)
 29         {
 30             if(g[i][j]==‘A‘||g[i][j]==‘S‘)
 31                 num[i][j]=nc++;
 32             if(g[i][j]==‘S‘)  //起点的编号
 33                 cnt=nc-1;
 34         }
 35     }
 36 }
 37 void bfs(int cx,int cy)  // 广搜确定最短距离
 38 {
 39     queue<Pos>Q;
 40     memset(vis,0,sizeof(vis));
 41     vis[cx][cy]=1;
 42     dis[cx][cy]=0;
 43     Q.push((Pos)
 44     {
 45         cx,cy
 46     });
 47     while(!Q.empty())
 48     {
 49         Pos e=Q.front();
 50         Q.pop();
 51         int x=e.x,y=e.y;
 52         if(num[x][y]!=-1)  //为-1时，即（x,y）为字母
 53             egde[num[cx][cy]][num[x][y]]=dis[x][y];
 54         for(int d=0; d<4; d++)
 55         {
 56             int sx=x+dirx[d];
 57             int sy=y+diry[d];
 58             if(sx<0&&sy<0&&sx>=y&&sy>=x)
 59                 continue;
 60             if(vis[sx][sy]||g[sx][sy]==‘#‘)
 61                 continue;
 62             vis[sx][sy]=1;
 63             dis[sx][sy]=dis[x][y]+1;
 64             Q.push((Pos)
 65             {
 66                 sx,sy
 67             });
 68         }
 69     }
 70 }
 71 int prim(int start) //套prim模板
 72 {
 73     int i,j,k,Min,ans=0;
 74     int d[MAX];
 75     bool visit[MAX];
 76     memset(visit,false,sizeof(visit));
 77     for(i=0; i<nc; i++)
 78         d[i]=egde[start][i];
 79     visit[start]=1;
 80     d[start]=0;
 81     for(i=0; i<nc-1; i++)
 82     {
 83         Min=INF,k=-1;
 84         for(j=0; j<nc; j++)
 85         {
 86             if(!visit[j]&&d[j]<Min)
 87             {
 88                 Min=d[j];
 89                 k=j;
 90             }
 91         }
 92         ans+=Min;
 93         visit[k]=1;
 94         for(j=0; j<nc; j++)
 95         {
 96             if(!visit[j]&&d[j]>egde[k][j])
 97                 d[j]=egde[k][j];
 98         }
 99     }
100     return ans;
101 }
102 int main()
103 {
104     cin>>t;
105     char s[500];
106     while(t--)
107     {
108         scanf("%d%d",&x,&y);
109         gets(s);  //注意：或许有无数空格
110         for(int i=0; i<y; i++)
111             gets(g[i]);
112         fun();
113         for(int i=0; i<y; i++)
114         {
115             for(int j=0; j<x; j++)
116             {
117                 if(g[i][j]==‘A‘||g[i][j]==‘S‘)
118                     bfs(i,j);
119             }
120         }
121         printf("%d\n",prim(cnt));
122     }
123     return 0;
124 }