差点被这个题目给整死了。。。。
题意：有一个图，‘#’是墙，A,S是需要走的点，找一条最短的路，这个路能连接所有的A和S；
做法：把所有的A和S看成一样的，用bfs求出所有的A,S之间的距离，然后用prim求出最小生成树。
整体来说就是BFS+prim
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define INF 10000000
using namespace std;
int map[101][101];
int xx[4]={1,-1,0,0};
int yy[4]={0,0,1,-1};
struct list
{int x;int y;
}point[1000];//所有的A,S所在的点
struct listt
{int x;int y;int len;
}bian[100000];//所有的A,S连成的边
struct listen
{int i;int j;int step;
}dist[100000],mo;
int num;
int number;
int f[100000];
int cmp(struct listt a,struct listt b)
{return a.len<b.len;
}
int find(int x)
{while(x!=f[x])x=f[x];return x;
}
int shu;
int bfs(int x,int y)
{int l,r;int visit[101][101];memset(visit,0,sizeof(visit));l=r=0;dist[l].i=point[x].x;dist[l].j=point[x].y;dist[l].step=0;visit[point[x].x][point[x].y]=1;r++;while(l<r){mo=dist[l];l++;int mi,mj,ms;mi=mo.i;mj=mo.j;ms=mo.step;if(mi==point[y].x&&mj==point[y].y){return ms;}int i;for(i=0;i<4;i++){if(visit[mi+xx[i]][mj+yy[i]]==0){if(map[mi+xx[i]][mj+yy[i]]!=-1){dist[r].i=mi+xx[i];dist[r].j=mj+yy[i];dist[r++].step=ms+1;visit[mi+xx[i]][mj+yy[i]]=1;}}}}
}
int main()
{int T,i;char str[10000];cin>>T;while(T--){int x,y;int n,j;cin>>x>>y;gets(str);memset(map,-1,sizeof(map));num=0;for(i=1;i<=x;i++){gets(str);n=strlen(str);for(j=0;j<n;j++){if(str[j]=='A'||str[j]=='S'){point[num].x=i;point[num++].y=j+1;map[i][j+1]=num;}if(str[j]==' '){map[i][j+1]=0;}}}number=0;for(i=0;i<num;i++){for(j=0;j<i;j++){bian[number].x=i;bian[number].y=j;bian[number++].len=bfs(i,j);}}sort(bian,bian+number,cmp);for(i=0;i<num;i++){f[i]=i;}int sum=0;int leap;leap=0;for(i=0;i<number;i++){if(find(bian[i].x)!=find(bian[i].y)){sum+=bian[i].len;f[find(bian[i].x)]=find(bian[i].y);leap++;}if(leap==num-1)break;}printf("%d\n",sum);}return 0;
}