题目链接：http://poj.org/problem?id=3026
题目大意：在一个y行 x列的迷宫中，有可行走的通路空格’ ‘，不可行走的墙’#’，还有两种英文字母A和S，现在从S出发，要求用最短的路径L连接所有字母，输出这条路径L的总长度。
解题思路：相当于所有的字母A和S都是结点，求连接这些结点的最小距离和，是最小生成树的题目。先用BFS求各点间的距离，然后再用Prim（Kruskal也可以）求出最小距离就可以了。
注意：输完行列m和n之后，后面有一堆空格，要用gets()去掉，题目有问题，超级坑。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=1e2+;
const int MAXN=1e2+;
const int INF=0x3f3f3f3f; int n,m;
int d[][]={,,,-,-,,,};
int num[N][N],cost[N][N],root[MAXN],low[MAXN];
bool vis[N][N],used[MAXN];
char str[N][N]; struct node{
int x,y,step;
node(){}
node(int x,int y,int step){
this->x=x;
this->y=y;
this->step=step;
}
}pre; //(x,y)点到各个点之间的最短距离
void bfs(int x,int y){
memset(vis,false,sizeof(vis));
queue<node>q;
q.push(node(x,y,));
vis[x][y]=true;
while(!q.empty()){
pre=q.front();
q.pop();
for(int i=;i<;i++){
int xx=pre.x+d[i][];
int yy=pre.y+d[i][];
int t=pre.step+;
if(x<=||y<=||x>n||y>m||vis[xx][yy]||str[xx][yy]=='#')
continue;
if(str[xx][yy]=='S'||str[xx][yy]=='A')
cost[num[x][y]][num[xx][yy]]=t;
vis[xx][yy]=true;
q.push(node(xx,yy,t));
}
}
}
//Prim求最小生成树
int Prim(int cnt){
memset(used,false,sizeof(used));
for(int i=;i<=cnt;i++){
low[i]=cost[][i];
}
used[]=true;
int ans=;
for(int i=;i<cnt;i++){
int k=-;
for(int j=;j<=cnt;j++){
if(!used[j]&&(k==-||low[k]>low[j])){
k=j;
}
}
if(k==-||low[k]==INF) return -;
ans+=low[k];
used[k]=true;
for(int j=;j<=cnt;j++){
if(!used[j]&&low[j]>cost[k][j])
low[j]=cost[k][j];
}
}
return ans;
} int main(){
int t;
char tmp[];
scanf("%d",&t);
while(t--){
memset(cost,0x3f,sizeof(cost));
scanf("%d%d",&m,&n);
//注意行列后面有一大堆空格要用gets()，出题人怕是个智。。。
gets(tmp);
int cnt=;
for(int i=;i<=n;i++){
gets(str[i]+);
for(int j=;j<=m;j++){
if(str[i][j]=='S'||str[i][j]=='A')
num[i][j]=++cnt;
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(str[i][j]=='S'||str[i][j]=='A'){
bfs(i,j);
}
}
}
printf("%d\n",Prim(cnt));
}
return ;
}