来源：
题意：说有一个迷宫，里面有一些外星人，外星人用字母A表示，#表示墙，不能走，空格可以走。从起点‘S’出发。在起点和A处可以分叉，问找到所有的外星人的最短路径是多少。
思路：此题其实不是太难了，可以先用bfs搜索图，然后建边，求出一点到另一点的距离，然后求最小生成树即可。最小生成树用prime和kruskal均可。关键是这道题输入需要注意。首先先输入的是列，然后是行。其次是输入列和行的后面有可能有空格，因此需要gets一下。还有就是输入字母时，因为有空格，所以不要用cin，用scanf。
代码：
#include#include #include #include #include using namespace std;#define CLR(arr,val) memset(arr,val,sizeof(arr))const int N = 55*2;int vis[N*2][N*2],map[N][N],father[N*2];struct edge{ int lp,rp,value;}ee[15050];struct point{ int x,y,step;}pp[N*2];int row,col,numedge,numpoint;int addx[4] = {0,0,1,-1};int addy[4] = {1,-1,0,0};bool fun(int x,int y){ if(map[x][y] >= 0 && !vis[x][y]) return true; return false;}void bfs(int posx,int posy,int id){ CLR(vis,0); queue qq; point newpp; newpp.x = posx; newpp.y = posy; newpp.step = 0; vis[posx][posy] = 1; qq.push(newpp); while(!qq.empty()){ point tpp = qq.front(); qq.pop(); int tx = tpp.x; int ty = tpp.y; for(int i = 1; i < numpoint; ++i){ if(pp[i].x == tx && pp[i].y == ty){ ee[numedge].lp = id; ee[numedge].rp = i; ee[numedge].value = tpp.step; numedge++; } } for(int i = 0; i < 4; ++i){ int newx = tx + addx[i]; int newy = ty + addy[i]; if(fun(newx,newy)){ vis[newx][newy] = 1; point newp; newp.x = newx; newp.y = newy; newp.step = tpp.step + 1; qq.push(newp); } } }}bool cmp(edge a,edge b){ return a.value < b.value;}int find(int x){ if(x == father[x]) return x; return find(father[x]);}bool Union_Set(int x,int y){ int fx = find(x); int fy = find(y); if(fx == fy) return false; else{ father[fx] = fy; return true; }}int kruskal(){ for(int i = 1; i <= numpoint; ++i) father[i] = i; int sum = 0; for(int i = 0; i < numedge; ++i){ int lx = ee[i].lp; int rx = ee[i].rp; if(Union_Set(lx,rx)) sum += ee[i].value; } return sum;}int main(){ //freopen("1.txt","r",stdin); int numcase; scanf("%d",&numcase); char ch[N]; while(numcase--){ CLR(map,-1); for(int i = 0; i < N*2; ++i){ pp[i].x = pp[i].y = pp[i].step = 0; } for(int i = 0; i < 15000; ++i){ ee[i].lp = ee[i].rp = ee[i].value = 0; } numpoint = 1; numedge = 0; scanf("%d%d",&col,&row); gets(ch); char ss; for(int i = 1; i <= row; ++i){ for(int j = 1; j <= col; ++j){ scanf("%c",&ss); if(ss == '#') map[i][j] = -1; else if(ss == ' ') map[i][j] = 0; else{ map[i][j] = 1; pp[numpoint].x = i; pp[numpoint].y = j; numpoint++; } } getchar(); } for(int i = 1;i < numpoint; ++i){ int posx = pp[i].x; int posy = pp[i].y; bfs(posx,posy,i); } sort(ee,ee+numedge,cmp); int ans = kruskal(); printf("%d\n",ans); } return 0 ;}