POJ - 3062 Borg Maze

Sample Input

2
6 5
##### 
#A#A##
# # A#
#S  ##
##### 
7 7
#####  
#AAA###
#    A#
# S ###
#     #
#AAA###
#####  
Sample Output

8
11

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stack>
  6 #include<math.h>
  7 #include<queue>
  8 #include<map>
  9 using namespace std;
 10 
 11 #define INF 0x3f3f3f3f
 12 #define N 1200
 13 
 14 int n,m,maps[N][N],b[N][N],dist[N],vis[N][N],viss[N];
 15 char s[N][N];
 16 int dir[4][2]={ {0,1},{0,-1},{1,0},{-1,0} };
 17 
 18 struct node
 19 {
 20     int x,y,step;
 21 }a[N];
 22 
 23 void Init()
 24 {
 25     int i,j;
 26     for(i=0;i<m*n;i++)
 27         dist[i]=INF;
 28         for(j=0;j<n*m;j++)
 29             maps[i][j]=(i==j)?0:INF;
 30 }
 31 
 32 void bfs(int ss,int x,int y)
 33 {
 34     int i;
 35 
 36     memset(vis,0,sizeof(vis));
 37     queue<node>Q;
 38     node B,Next,Now;
 39     B.x=x;
 40     B.y=y;
 41     B.step=0;
 42     Q.push(B);
 43     vis[x][y]=1;
 44 
 45     while(Q.size())
 46     {
 47         Now=Q.front();
 48         Q.pop();
 49 
 50         if(s[Now.x][Now.y]>=‘A‘&&s[Now.x][Now.y]<=‘Z‘)
 51             maps[ss][b[Now.x][Now.y]]=Now.step;
 52 
 53         for(i=0;i<4;i++)
 54         {
 55             Next.x=Now.x+dir[i][0];
 56             Next.y=Now.y+dir[i][1];
 57             if(Next.x<m&&Next.x>=0&&Next.y<n&&Next.y>=0&&vis[Next.x][Next.y]==0&&s[Next.x][Next.y] != ‘#‘)
 58             {
 59                 vis[Next.x][Next.y]=1;
 60                 Next.step=Now.step+1;
 61                 Q.push(Next);
 62             }
 63         }
 64     }
 65 }
 66 
 67 int Prim(int e)
 68 {
 69     int i,j;
 70    viss[1]=1;
 71    for(int i=1;i<=e;i++)
 72         dist[i]=maps[1][i];
 73     int sum=0;
 74    for(i=1;i<=e;i++)
 75    {
 76        int Min=INF,index=-1;
 77 
 78        for(j=1;j<=e;j++)
 79         if(!viss[j]&&Min>dist[j])
 80        {
 81            Min=dist[j];
 82            index=j;
 83        }
 84        if(index==-1)break;
 85        sum+=Min;
 86        viss[index]=1;
 87 
 88        for(j=1;j<=e;j++)
 89         if(!viss[j]&&dist[j]>maps[index][j])
 90         dist[j]=maps[index][j];
 91    }
 92 
 93    return sum;
 94 }
 95 
 96 int main()
 97 {
 98     int T,i,j;
 99 
100     scanf("%d", &T);
101 
102     while(T--)
103     {
104         memset(a,0,sizeof(a));
105         memset(viss,0,sizeof(viss));
106 
107         scanf("%d%d ", &n,&m);
108         Init();
109 
110         int cnt=1;
111         for(i=0;i<m;i++)
112         {
113             gets(s[i]);
114             for(j=0;j<n;j++)
115             {
116                 if(s[i][j]<=‘Z‘&&s[i][j]>=‘A‘)
117                     b[i][j]=cnt++;///记录cnt号动点位置
118             }
119         }
120 
121         for(i=0;i<m;i++)
122         {
123             for(j=0;j<n;j++)
124             {
125                 if(s[i][j]<=‘Z‘&&s[i][j]>=‘A‘)
126                     bfs(b[i][j],i,j);///搜索，记录各个点之间步数
127             }
128         }
129 
130         int ans=Prim(cnt-1);///最小生成树求最终值
131         printf("%d\n", ans);
132     }
133 }