RT，Udebug上的数据全过了，就是过不了UVA的；

如有大佬帮助蒟蒻解决问题，蒟蒻V您￥5

代码如下：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
typedef pair<int,PII> PIP;
const int N=1010;
int t,n,m,cnt,dist[N][N],fa[N],ans,tot,b[N][N];
int dx[]={0,-1,0,1,0};
int dy[]={0,0,1,0,-1};
char a[N][N];
string str;
PII pos[N];
queue<PIP> q;
bool st[N][N];
struct node{
	int x,y,leng;
}edge[N*N];
bool cmp(node u,node v){
	return u.leng<v.leng;
}
void bfs(int x,int y,int num){
	while(q.size()){
		q.pop();
	}
	q.push(PIP(0,PII(x,y)));
	while(q.size()){
		PIP t=q.front();
		q.pop();
		if(st[t.second.first][t.second.second]==true){
			continue;
		}
		st[t.second.first][t.second.second]=true;
		for(int i=1;i<=4;i++){
			int sx=t.second.first+dx[i],sy=t.second.second+dy[i];
			if(sx<=0||sy<=0||sx>n||sy>m||a[sx][sy]=='#'||st[sx][sy]==true){
				continue;
			}
			if(a[sx][sy]=='S'||a[sx][sy]=='A'){
				dist[num][b[sx][sy]]=min(dist[num][b[sx][sy]],t.first+1);
			}
//			cout<<t.second.first<<" , "<<t.second.second<<" -> "<<sx<<" , "<<sy<<" : "<<t.first+1<<endl;
			q.push(PIP(t.first+1,PII(sx,sy)));
		}
	}
}
int find(int x){
	if(fa[x]==x){
		return x;
	}
	return fa[x]=find(fa[x]);
}
void hb(int x,int y){
	fa[y]=x;
}
int main(){
	freopen("UVA10307.in","r",stdin);
	freopen("UVA10307.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&m,&n);
		char empty[100];
		gets(empty);
		cnt=ans=tot=0;
		memset(a,' ',sizeof a);
		memset(pos,0,sizeof pos);
		for(int i=1;i<=n;i++){
			getline(cin,str);
			for(int j=1;j<=m;j++){
				a[i][j]=str[j-1];
				if(a[i][j]=='A'||a[i][j]=='S'){
					pos[++cnt].first=i,pos[cnt].second=j;
					b[i][j]=cnt;
				}
//				cout<<a[i][j]<<" ";
			}
//			cout<<endl;
		}
		for(int i=1;i<=cnt;i++){
//			cout<<i<<" : "<<pos[i].first<<" , "<<pos[i].second<<endl;
			for(int j=1;j<=cnt;j++){
				dist[i][j]=0x3f3f3f3f;
			}
		}
		for(int i=1;i<=cnt;i++){
			fa[i]=i;
			bfs(pos[i].first,pos[i].second,i);
			for(int j=1;j<=n;j++){
				for(int k=1;k<=m;k++){
					st[j][k]=false;
				}
			}
		}
		for(int i=1;i<=cnt;i++){
			for(int j=1;j<=cnt;j++){
				edge[++tot].x=i,edge[tot].y=j,edge[tot].leng=dist[i][j];
//				cout<<edge[tot].x<<" , "<<edge[tot].y<<" : "<<edge[tot].leng<<endl;
			}
		}
		sort(edge+1,edge+tot+1,cmp);
		int blocnt=cnt;
		for(int i=1;i<=tot;i++){
			if(blocnt==1){
				break;
			}
			int fx=find(edge[i].x),fy=find(edge[i].y);
			if(fx!=fy){
				hb(fx,fy);
				blocnt--;
				ans+=edge[i].leng;
//				cout<<pos[edge[i].x].first<<" , "<<pos[edge[i].x].second<<" -> "<<pos[edge[i].y].first<<" , "<<pos[edge[i].y].second<<" : "<<edge[i].leng<<endl;
			}
		}
		printf("%d\n",ans);
	}
	printf("\n");
}