题意：
题目我一开始一直读不懂。有一个会分身的人，要在一个地图中踩到所有的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 << " "; #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 ' ' #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; //2147483647 const ll nmos = 0x80000000; //-2147483648 const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; //18 const int mod = 1e9+7; const double esp = 1e-8; const double PI=acos(-1.0); template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } /*-----------------------showtime----------------------*/ const int maxn = 2009; int fa[maxn*maxn],tot = 0,cnt = 0,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[5][5] = { {1,0},{0,1},{-1,0},{0,-1} }; void bfs(int x,int y){ for(int i=0; i<m; i++){ for(int j=0; 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] = 0; while(!q.empty()){ pii tmp = q.front();q.pop(); int tx = tmp.fi,ty = tmp.se; for(int i=0; i<4; i++){ int nx = tx + nt[i][0]; int ny = ty + nt[i][1]; if(nx <0||nx >= m || ny <0 || 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]+1); 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[0]); tot = 0; for(int i=0; i<m; i++){ getline(cin,str[i]); } for(int i=0; i<m; i++){ for(int j=0; j<n; j++){ if(str[i][j] == 'A' || str[i][j] == 'S')bfs(i,j); } } for(int i=0; i<=n*m*2; i++)fa[i] = i; sort(e+1,e+1+tot,cmp); int ans = 0; for(int i=1; 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 0; } /* ##### #A#A## # # A# #S ## ##### ##### #AAA### # A# # S ### # # #AAA### ##### */