[kuangbin带你飞]专题六最小生成树 J - Borg Maze

布满荆棘的人生 2023-08-17 15:41 115阅读 0赞

# J - Borg Maze #

题目链接：[https://vjudge.net/contest/66965\#problem/J][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\n",kru(num));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11285802.html

[https_vjudge.net_contest_66965_problem_J]: https://vjudge.net/contest/66965#problem/J