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

题目链接：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;
}