J - Borg Maze
题目链接：https://vjudge.net/contest/66965#problem/J
题目：
博格是一个非常强大的种族，它来自银河系的三角洲象限。博格集体是用来描述博格文明群体意识的术语。每个博格人都通过复杂的子空间网络与集体联系，确保每个成员得到持续的监督和指导。
你的任务是帮助博格（是的，真的）通过开发一个程序，帮助博格估计扫描迷宫的最低成本，以便同化隐藏在迷宫中的外星人，在北部，西部，东部和南部移动脚步。棘手的是，搜索的开始是由100多个人组成的。每当外星人被同化时，或者在搜索开始时，该群体可能会分成两组或更多组（但他们的意识仍然是集体的）。搜索迷宫的成本被定义为搜索中涉及的所有组所覆盖的总距离。也就是说，如果原始组走五步，则分成两组，每组步行三步，总距离为11 = 5 + 3 + 3。
输入
在输入的第一行有一个整数，N <= 50，给出输入中的测试用例数。每个测试用例以包含两个整数x，y的行开始，使得1 <= x，y <= 50.然后，跟随y行，每行x个字符。对于每个角色，空格“`”代表开放空间，哈希标记“＃”代表障碍墙，大写字母“A”代表外星人，大写字母“S”代表''代表搜索的开始。迷宫的周长总是关闭的，即没有办法从“S”的坐标中走出来。迷宫中至多有100个外星人，每个人都可以到达。
产量
对于每个测试用例，输出一行包含成功搜索迷宫的最小成本，不留外来人。
样本输入
2
6 5
#####
＃A＃A ##
＃ ＃ 一个＃
#S ##
#####
7 7
#####
#AAA ###
＃ 一个＃
＃S ###
##
#AAA ###
#####
样本输出
8
11
思路：这题一开始没看懂啥意思，百度了看的，先bfs求出每个A到S的距离，然后用最小生成树求出最小边权和即可
// // Created by hanyu on 2019/8/1. // #include <algorithm> #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <set> #include<math.h> using namespace std; typedef long long ll; const int maxn=2e6+7; int father[maxn]; int book[600][600],point[600][600]; char str[600][600]; int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; struct Point{ int x,y,step; }; struct Node{ int u,v,w; bool operator<(const Node &other)const{ return this->w<other.w; } }node[maxn]; int find(int x) { if(x==father[x]) return x; return father[x]=find(father[x]); } int n,m,num,cnt; void bfs(int sx,int sy) { memset(book,0,sizeof(book)); Point now,next; queue<Point>qu; now.x=sx; now.y=sy; now.step=0; book[sx][sy]=1; qu.push(now); while(!qu.empty()) { now=qu.front(); qu.pop(); for(int i=0;i<4;i++) { next.x=now.x+dir[i][0]; next.y=now.y+dir[i][1]; next.step=now.step+1; if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&str[next.x][next.y]!='#'&&!book[next.x][next.y]) { book[next.x][next.y]=1; qu.push(next); if(str[next.x][next.y]=='S'||str[next.x][next.y]=='A') { node[num].u=point[sx][sy]; node[num].v=point[next.x][next.y]; node[num++].w=next.step; } } } } } int kru(int n) { int res=0; for(int i=0;i<cnt;i++) father[i]=i; for(int i=0;i<n;i++) { int uu=find(node[i].u); int vv=find(node[i].v); if(uu==vv) continue; else { father[uu]=vv; res+=node[i].w; } } return res; } int main() { int T; scanf("%d",&T); char str1[maxn]; while(T--) { scanf("%d%d",&m,&n); gets(str1); cnt=0; num=0; memset(point,0,sizeof(point)); for(int i=0;i<n;i++) { gets(str[i]); for(int j=0;j<m;j++) { if(str[i][j]=='S'||str[i][j]=='A') point[i][j]=cnt++; } } for(int i=0;i<n;i++) { for (int j = 0; j < m; j++) { if(str[i][j]=='A'||str[i][j]=='S') bfs(i,j); } } sort(node,node+num); printf("%d ",kru(num)); } return 0; }