这道题相当坑，不仅仅是数据里面有多余的空格，而且是有102个可联通点才对。

题目的话，说实话我没看懂，我从例子猜出的模型，我的做法是先用搜索找出各点之间的最短距离，然后用最小生成树得出权值即为结果。

代码如下：

bfs+kruskal，稀疏图应该是我的bfs处理得不好，不是0ms过

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
using namespace std;
int map[52][52],father[102],liantong[103][103];
struct n1
{
	int x,y,step;
};
n1 dian[102];
n1 path[6000];
int bfs(int i,int k,int row,int line)
{
	n1 temp1,temp2;
	queue<n1>q1;
	int vis[52][52],j;
	memset(vis,0,sizeof(vis));
	temp1=dian[i];
	temp1.step=0;
	q1.push(temp1);
	vis[temp1.x][temp1.y]=1;
	while(q1.size()!=0)
	{
		temp1=q1.front();
		q1.pop();
		for(j=1;j<=4;j++)
		{
			temp2=temp1;
			temp2.step++;
			if(j==1)
			temp2.x--;
			else if(j==2)
			temp2.x++;
			else if(j==3)
			temp2.y--;
			else
			temp2.y++;
			if(map[temp2.x][temp2.y]!=0&&vis[temp2.x][temp2.y]==0&&liantong[i][map[temp2.x][temp2.y]]==0)
			{
				q1.push(temp2);
				vis[temp2.x][temp2.y]=1;
				if(map[temp2.x][temp2.y]>0)
				{
					k++;
					path[k].x=i;
					path[k].y=map[temp2.x][temp2.y];
					path[k].step=temp2.step;
					liantong[i][map[temp2.x][temp2.y]]=liantong[map[temp2.x][temp2.y]][i]=1;
				}
			}
		}
	}
	return k;
}
int find(int i)
{
	while(i!=father[i])
	i=father[i];
	return i;
}
int cmp(n1 a,n1 b)
{
	return a.step<b.step;
}
int kruskal(int v,int e)
{
	int temp1,temp2,i,num_bian,sum;
	for(i=1;i<=v;i++)
	father[i]=i;
	sort(path+1,path+1+e,cmp);
	sum=num_bian=0;
	v--;
	for(i=1;num_bian<v;i++)
	{
		temp1=find(path[i].x);
		temp2=find(path[i].y);
		if(temp1!=temp2)
		{
			num_bian++;
			sum+=path[i].step;
			if(temp1>temp2)
			temp1^=temp2^=temp1^=temp2;
			father[temp2]=temp1;
		}
	}
	return sum;
}
int main()
{
	int i,n,line,row,j,k;
	char data[52][52],temp[1000];
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d%d",&line,&row);
		gets(temp);
		for(i=0;i<row;i++)
		gets(data[i]);
		k=0;
		memset(map,0,sizeof(map));
		for(i=0;i<row;i++)
		for(j=0;j<line;j++)
		{
			if(data[i][j]=='A'||data[i][j]=='S')
			{
				map[i+1][j+1]=++k;
				dian[k].x=i+1;
				dian[k].y=j+1;
			}
			else if(data[i][j]==' ')
			map[i+1][j+1]=-1;
		}
		int bian=0;
		memset(liantong,0,sizeof(liantong));
		for(i=1;i<=k;i++)
		bian=bfs(i,bian,row,line);
		printf("%d\n",kruskal(k,bian));
	}
	return 0;
}