题意：
题目我一开始一直读不懂。有一个会分身的人，要在一个地图中踩到所有的A，这个人可以在出发地或者A点任意分身，问最少要走几步，这个人可以踩遍地图中所有的A点。
思路：
感觉就算读懂了题目，也比较难想到这用到了最小生成树的知识，因为可以分身，所以每个点可以向其他点都连上边。可以用bfs预处理出所有的S点，A点的连线，再跑一遍最小生成树，即可得出答案。这里有几点注意，一开始我bfs没有记录step，而是直接找到一点后算曼哈顿距离，这是不对的，因为可能是绕了一个圈到了这个点。还有读完数字再读字符串的话，以后尽量用getline(cin,str),防止题目数据后面多几个空格。
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert>
using namespace std;
//#pragma GCC optimize(3)
//#pragma comment(linker, "/STACK:102400000,102400000") //c++
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue typedef long long ll;
typedef unsigned long long ull; typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3; //priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl '\n' #define OKC ios::sync_with_stdio(false);cin.tie(0)
#define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行
#define REP(i , j , k) for(int i = j ; i < k ; ++i)
//priority_queue<int ,vector<int>, greater<int> >que; const ll mos = 0x7FFFFFFF; //
const ll nmos = 0x80000000; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //
const int mod = 1e9+;
const double esp = 1e-;
const double PI=acos(-1.0); template<typename T>
inline T read(T&x){
x=;int f=;char ch=getchar();
while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x=f?-x:x;
} /*-----------------------showtime----------------------*/ const int maxn = ;
int fa[maxn*maxn],tot = ,cnt = ,t,n,m;
bool vis[maxn][maxn];
int dis[maxn][maxn];
struct node
{
int x,y;
}p[maxn];
struct eg{
int u,v,dis;
}e[maxn*maxn];
bool cmp(eg a,eg b){
return a.dis < b.dis;
}
int find(int x){
if(fa[x] == x)return x;
return fa[x] = find(fa[x]);
}
string str[maxn]; int nt[][] = {
{,},{,},{-,},{,-}
};
void bfs(int x,int y){
for(int i=; i<m; i++){
for(int j=; j<n; j++){
dis[i][j] = inf;
vis[i][j] =false;
}
}
queue<pii>q;
q.push(pii(x,y));
vis[x][y] = true;
dis[x][y] = ;
while(!q.empty()){
pii tmp = q.front();q.pop();
int tx = tmp.fi,ty = tmp.se;
for(int i=; i<; i++){
int nx = tx + nt[i][];
int ny = ty + nt[i][];
if(nx <||nx >= m || ny < || ny >=n)continue;
if(str[nx][ny] == '#')continue;
if(vis[nx][ny])continue;
vis[nx][ny] = true;
dis[nx][ny] = min(dis[nx][ny], dis[tx][ty]+);
if(str[nx][ny] == 'A' || str[nx][ny] == 'S'){
e[++tot].u = x * n + y;
e[tot].v = nx * n + ny;
e[tot].dis = dis[nx][ny];
// if(x == 1 && y==1){
// cout<<e[tot].u<<" "<<e[tot].v<<" "<<e[tot].dis<<endl;
// }
}
q.push(pii(nx,ny));
}
}
}
int main(){
OKC;
cin>>t;
while(t--){
cin>>n>>m;
getline(cin,str[]);
tot = ;
for(int i=; i<m; i++){
getline(cin,str[i]);
}
for(int i=; i<m; i++){
for(int j=; j<n; j++){
if(str[i][j] == 'A' || str[i][j] == 'S')bfs(i,j);
}
}
for(int i=; i<=n*m*; i++)fa[i] = i;
sort(e+,e++tot,cmp); int ans = ;
for(int i=; i<=tot; i++){
int fx = find(e[i].u);
int fy = find(e[i].v);
if(fx != fy){
ans += e[i].dis;
fa[fx] = fy;
// debug(e[i].dis);
}
}
cout<<ans<<endl;
}
return ;
} /*
#####
#A#A##
# # A#
#S ##
##### #####
#AAA###
# A#
# S ###
# #
#AAA###
#####
*/
POJ 3026