传送门：Borg Maze
题意：有一个迷宫，里面有一些外星人，外星人用字母A表示，#表示墙，不能走，空格可以走，从S点出发，在起点S和A处可以分叉走，问找到所有的外星人的最短路径是多少?
分析：分别bfs由S和所有A出发到其他点的距离，然后建好图进行最小生成树处理即可。
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #define LL long long #define mod 100000000 #define inf 0x3f3f3f3f #define eps 1e-6 #define N 110 #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define PII pair<int,int> using namespace std; struct edge { int u,v,w; edge() {} edge(int u,int v,int w):u(u),v(v),w(w){} bool operator<(const edge &a)const { return w<a.w; } } e[N*N]; struct node { int x,y,step; node(){} node(int x,int y,int step):x(x),y(y),step(step){} }; int fa[N],tot,total; char str[N][N]; int num[N][N],vis[N][N],n,m; int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } int MST(int n) { int ans=0; for(int i=1;i<=n;i++)fa[i]=i; sort(e,e+tot); for(int i=0; i<tot; i++) { int a=find(e[i].u); int b=find(e[i].v); if(a==b)continue; fa[a]=b; ans+=e[i].w; } return ans; } bool judge(int a,int b) { return a>=1&&a<=n&&b>=1&&b<=m&&str[a][b]!='#'&&!vis[a][b]; } void bfs(int x,int y) { queue<node>que; while(!que.empty())que.pop(); FILL(vis,0); vis[x][y]=1; que.push(node(x,y,0)); while(!que.empty()) { node now=que.front();que.pop(); for(int i=-1;i<=1;i++) for(int j=-1;j<=1;j++) { if(i+j==0||i==j)continue; int a=now.x+i,b=now.y+j,step=now.step+1; if(judge(a,b)) { if(str[a][b]=='A'||str[a][b]=='S') { e[tot++]=edge(num[x][y],num[a][b],step); } vis[a][b]=1; que.push(node(a,b,step)); } } } } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&m,&n); gets(str[0]); for(int i=1;i<=n;i++) gets(str[i]); total=0;tot=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(str[i][j]=='A'||str[i][j]=='S') { num[i][j]=++total; } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(str[i][j]=='A'||str[i][j]=='S') { bfs(i,j); } } printf("%d ",MST(total)); } }