题目说从S开始，在S或者A的地方可以分裂前进。 想一想后发现就是求一颗最小生成树。
首先bfs预处理得到每两点之间的距离，我的程序用map做了一个映射，将每个点的坐标映射到1-n上，这样建图比较方便。
然后一遍prime就够了。注意用gets（）读入地图的时候，上面还要用一个gets（）接住无用的空格。。（为啥不用getchar？0 0，看了讨论版才知道，
因为空格很多………………）
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
char map1[55][55];
int head,tail;
int x,y;
map<int,int> M;
struct node
{
int x,y;
int dis;
}q[100000];
int top;
int start;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int dis[150][150];
bool vis[150][150];
void bfs(int k,int st)
{
memset(vis,0,sizeof(vis));
head=tail=0;
node tmp,tt;
tmp.x=st/x;
tmp.y=st%x;
vis[tmp.x][tmp.y]=1;
tmp.dis=0;
int tot=0;
q[tail++]=tmp;
int f;
while(head<tail)
{
tmp=q[head];
for(int d=0;d<4;d++)
{
tt=tmp;
tt.x+=dx[d];
tt.y+=dy[d];
tt.dis++;
if(map1[tt.x][tt.y]!='#'&&!vis[tt.x][tt.y])
{
vis[tt.x][tt.y]=1;
if(f=M[tt.x*x+tt.y])
{
tot++;
dis[k][f]=tt.dis;
}
q[tail++]=tt;
if(tot==top) return;
}
}
head++;
}
}
int n,sum;
int visit[150],d[150];
void prime(int n)
{
int i,j,min,v;
sum=0;
for(i=1;i<=n;i++)
{
d[i]=dis[1][i];
visit[i]=0;
}
visit[1]=1;
for(i=1;i<n;i++)
{
min=INF;
v=1;
for(j=1;j<=n;j++)
{
if(!visit[j]&&min>d[j])
{
min=d[j];
v=j;
}
}
sum+=min;
visit[v]=1;
for(j=1;j<=n;j++)
{
if(!visit[j]&&dis[v][j]<d[j])
d[j]=dis[v][j];
}
}
}
int main()
{
char tmp[1000];
int cas;
scanf("%d",&cas);
while(cas--)
{
memset(dis,0x3f,sizeof(dis));
M.clear();
top=0;
scanf("%d%d",&x,&y); gets(tmp);//接住空格
for(int i=0;i<y;i++){
gets(map1[i]);
}
for(int i=1;i<y-1;i++)
{
for(int j=1;map1[i][j];j++)
{
if(map1[i][j]=='A'||map1[i][j]=='S')
{
top++;
if(map1[i][j]=='S') start=top;
M[i*x+j]=top;
dis[top][top]=0; }
}
}
for(int i=1;i<y-1;i++)
{
for(int j=1;map1[i][j];j++)
{
if(map1[i][j]=='A'||map1[i][j]=='S')
{
bfs(M[i*x+j],i*x+j);
}
}
}
prime(top);
printf("%d\n",sum);
}
return 0;
}