题意：
给定一个迷宫，‘#’代表墙，空格代表空地，S开始，到达所有的A，求最少的步数。
题解：
最小生成树：
但是任意点间的距离需要BFS搜索出来。
注意：迷宫的读取用gets（）读一整行！（有空格）
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<vector>
#include<functional>
#include<utility>
#include<set>
#include<map>
#include<cmath>
#include<cctype>using namespace std;
const int maxn=110;struct edge
{int u,v,cost;edge(int u,int v,int d):u(u),v(v),cost(d) {}bool operator<(const edge& a)const{return cost<a.cost;}
};char mp[maxn][maxn];
int a[maxn][maxn];vector<edge>es;int pa[maxn];
int N;
int n,m;int dx[]= {0,0,1,-1};
int dy[]= {1,-1,0,0};int findset(int x)
{return pa[x]<0?x:pa[x]=findset(pa[x]);
}int kk()
{int cnt=0;int ans=0;memset(pa,-1,sizeof(pa));sort(es.begin(),es.end());for(int i=0; i<es.size(); i++){int u=es[i].u,v=es[i].v;if(findset(u)!=findset(v)){ans+=es[i].cost;//cout<<es[i].cost;pa[findset(u)]=findset(v);if(++cnt>=N-1)break;}}return ans;
}bool vis[maxn][maxn];
struct node
{int x,y,num;
};
void bfs(int i,int j)
{memset(vis,false,sizeof(vis));queue<node>q;node ta,tb;ta.x=i;ta.y=j;ta.num=0;vis[i][j]=true;q.push(ta);while(!q.empty()){tb=q.front();q.pop();if(a[tb.x][tb.y]!=-1){int u=a[i][j];int v=a[tb.x][tb.y];int dist=tb.num;es.push_back(edge(u,v,dist));//cout<<u<<" "<<v<<" "<<dist<<endl;}for(int k=0; k<4; k++){ta.x=tb.x+dx[k];ta.y=tb.y+dy[k];if(ta.x<0||ta.x>=n||ta.y<0||ta.y>=m)continue;if(mp[ta.x][ta.y]=='#'||vis[ta.x][ta.y])continue;ta.num=tb.num+1;vis[ta.x][ta.y]=true;q.push(ta);}}}int main()
{int T;cin>>T;while(T--){es.clear();memset(a,-1,sizeof(a));scanf("%d %d",&m,&n);gets(mp[0]);int cnt=0;for(int i=0; i<n; i++){gets(mp[i]);for(int j=0; j<m; j++)if(mp[i][j]=='S'||mp[i][j]=='A')a[i][j]=cnt++;}for(int i=0; i<n; i++)for(int j=0; j<m; j++)if(a[i][j]!=-1)bfs(i,j);N=cnt;cout<<kk()<<endl;}
}