题目链接：
POJ 3026 Borg Maze
题意：
有一个n行*m列的字符矩阵，A代表一个需要同化的点，S代表起始点，#代表障碍，不可通过，‘ ’空格是可行的。
从s开始需要同化所有的A，并且一个A被同化后也具有了同化其他A的能力。输入保证S可到达任意一个A。
问从s开始同化所有的A需要多少步？
分析：
将所有的A和S看成一个个点，也就是求将这些点连通的最小生成树。
然后问题就是任意两点间的权值，并且这个权值是两点间所有可达路径中的最短路径。
对每一个点用一次BFS就好了，再用Prim Algorithm就行了。
注意：
n,m后面可能不止一个空格，太坑了……
//840K 110MS
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;const int maxn=150;
const int INF=0x3f3f3f3f;int dir[4][2]={
{-1,0},{
1,0},{
0,-1},{
0,1}};//上下左右四个方向int T,n,len,tot;
int cost[maxn][maxn],vis[maxn][maxn],dis[maxn],vvis[maxn];
char map[maxn][maxn],s[maxn];struct Point{int x,y;
}point[maxn];struct Node{int x,y,step;
}cur,nextnode;void bfs(int u,int sr,int sc)//u,sr,sc分别是点编号和点所在行列
{queue<Node> q;cur.x=sr;cur.y=sc;cur.step=0;memset(vis,0,sizeof(vis));//标记图上各点访问情况vis[cur.x][cur.y]=1;cost[u][u]=0;q.push(cur);while(!q.empty()){cur=q.front();q.pop();for(int i=0;i<4;i++){int x=cur.x+dir[i][0];int y=cur.y+dir[i][1];if(x<0||y<0||x>=n||y>=len||vis[x][y]||map[x][y]=='#') continue;//printf("%d %d\n",x,y);nextnode.x=x;nextnode.y=y;nextnode.step=cur.step+1;vis[x][y]=1;for(int j=0;j<tot;j++){
//因为图上每个可访问点都只访问一次，所以访问到一个点就是两点间的距离if(point[j].x==x&&point[j].y==y){cost[u][j]=nextnode.step;}}q.push(nextnode);}}
}int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);
#endifscanf("%d",&T);while(T--){tot=1;scanf("%d%d",&len,&n);for(int i=0;i<n;i++){gets(s);//一开始这里写getchar();结果WA了，看Discuss才知道原来后台数据len,n后面还有空格for(int j=0;j<len;j++){scanf("%c",&map[i][j]);if(map[i][j]=='A'){point[tot].x=i;point[tot].y=j;tot++;}else if(map[i][j]=='S')//起点下标为0{point[0].x=i;point[0].y=j;}}}/*for(int i=0;i<n;i++){for(int j=0;j<len;j++){putchar(map[i][j]);}printf("\n");}*/for(int i=0;i<tot;i++)//对每一点求相应边长,由于起点可到达任意一点，那么任意两点间都是连通的bfs(i,point[i].x,point[i].y);/*for(int i=0;i<tot;i++){for(int j=0;j<tot;j++){printf("%d ",cost[i][j]);}printf("\n");}*///Prim Algorithmmemset(vvis,0,sizeof(vvis));vvis[0]=1;int ans=0;for(int i=0;i<tot;i++)//一共有tot个点dis[i]=cost[0][i];for(int i=1;i<tot;i++){int k=-1;int tmp=INF;for(int j=0;j<tot;j++){if(!vvis[j]&&dis[j]<tmp){k=j;tmp=dis[j];}}vvis[k]=1;ans+=tmp;for(int j=0;j<tot;j++){if(!vvis[j]&&dis[j]>cost[k][j]) dis[j]=cost[k][j];}}printf("%d\n",ans);}return 0;
}