J - Borg Maze

题目链接：

题目：

博格是一个非常强大的种族，它来自银河系的三角洲象限。博格集体是用来描述博格文明群体意识的术语。每个博格人都通过复杂的子空间网络与集体联系，确保每个成员得到持续的监督和指导。

    你的任务是帮助博格（是的，真的）通过开发一个程序，帮助博格估计扫描迷宫的最低成本，以便同化隐藏在迷宫中的外星人，在北部，西部，东部和南部移动脚步。棘手的是，搜索的开始是由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 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include
           
            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
            
             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
             
              =0&&next.y