【POJ 3026】Borg Maze（BFS+Prime算法）

忘是亡心i 2022-02-15 12:17 200阅读 0赞

题目链接：[http://poj.org/problem?id=3026][http_poj.org_problem_id_3026]

### 题意： ###

有一个迷宫，迷宫里面有一些外星人，你需要通过扫描迷宫来同化隐藏在迷宫中的外星人，迷宫里的S是起点，搜索的开始是由多个人组成的，搜索过程中，在外星人处或搜索开始的地方，该群体可能会分成两组或更多组。求同化所有外星人所需要的最小步数。

### 思路： ###

刚开始一直在纠结分组是啥意思，为嘛要分组，咋分组才能使成本最小，后来看了大佬的博客才知道这句没啥用，主要是为了把它抽象成最小生成树。

这题可以这样理解，一群外星人在一张地图当中，你有不小于外星人数量的人手，你要找到他们，并且你可以在找到外星人或出发时将人手分成任意两部分（这是不是就有点儿像最小生成树里的Prime算法）。

嗯 ，这样的话，主要问题就在于如何求两点之间的距离了，这类似于迷宫里求起点到终点的距离，因此就需要用bfs算法求迷宫里面两点之间的距离。下面可以结合代码走一遭。

噢 对，这道题里面还藏了一个自我感觉良好的坑，（据说做了这题的娃儿都被它成功坑到了，当然，我也没跑掉）输入迷宫的x，y后面还有些空格，不得不说出题人真的很淘气

### My Code： ###

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<queue>
    #include<math.h>
    #include<set>
    using namespace std;
    #define INF 1e9
    typedef long long ll;
    int dis[105][105],d[105],flag[105],n;
    void Prime()///最小生成树
    {
        memset(flag,0,sizeof(flag));
        for(int i =1; i <= n; i++)
            d[i] = dis[1][i];
        d[1] = 0;
        flag[1] = 1;
        int ans = 0;
        for(int i = 1; i < n; i++)
        {
            int minn = INF,k;
            for(int j = 1; j <= n; j++)
            {
                if(d[j] < minn && flag[j] == 0)
                {
                    minn = d[j];
                    k = j;
                }
            }
            flag[k] = 1;
            ans += d[k];
            for(int j = 1; j <= n; j++)
                d[j] = min(d[j],dis[k][j]);
        }
        printf("%d\n",ans);
    }
    struct point
    {
        int x,y,step;
    };
    int vis[55][55],node[55][55],col,row;
    ///vis标记是否走过，node用来标记外星人A和起点S
    int dir[4][2] = {
       {1,0},{-1,0},{0,1},{0,-1}};
    char ch[55][55];
    void bfs(int i,int j)///求出每两点之间的距离
    {
        memset(vis,0,sizeof(vis));
        point start;
        start.x = i;
        start.y = j;
        start.step = 0;
        vis[start.x][start.y] = 1;
        point cur,nxt;
        queue<point> q;
        q.push(start);
        while(!q.empty())///遍历整个迷宫，求出起点到其他各点的距离
        {
            cur = q.front();
            q.pop();
            if(node[cur.x][cur.y]) dis[node[start.x][start.y]][node[cur.x][cur.y]] = cur.step;///碰到一个点，记录他们俩之间的距离
            for(int i = 0; i < 4; i++)
            {
                nxt.x = cur.x + dir[i][0];
                nxt.y = cur.y + dir[i][1];
                nxt.step = cur.step +1;
                if(nxt.x >= 0 &&nxt.x < row && nxt.y >= 0 && nxt.y < col && ch[nxt.x][nxt.y] != '#' && vis[nxt.x][nxt.y] == 0)
                {
                    vis[nxt.x][nxt.y] = 1;
                    q.push(nxt);
                }
            }
        }
        return;
    }
    int main()
    {
        int t;
        cin >> t;
        while(t--)
        {
            char s[10000];
            scanf("%d%d",&col,&row);
            gets(s);///注意输入行列后面还有空格，确保自己代码没问题但还是wa的看看是否加了这句
            memset(ch,'\0',sizeof(ch));
            memset(node,0,sizeof(node));
            int cunt = 1;
            for(int i = 0; i < row; i++)
            {
                getchar();///吃掉多余的换行符
                scanf("%[^\n]",ch[i]);
                for(int j =0; j < col; j++)
                {
                    if(ch[i][j] == 'S' || ch[i][j] == 'A')
                        node[i][j] = cunt++;
                }
            }
            n = cunt -1;
            for(int i = 0; i < row; i++)
            {
                for(int j = 0; j < col; j++)
                {
                    if(node[i][j]) bfs(i,j);///以点（i，j）为起点遍历整个迷宫
                }
            }
            Prime();
        }
    
        return 0;
    }

[http_poj.org_problem_id_3026]: http://poj.org/problem?id=3026