POJ 3026 Borg Maze

题目链接：kuangbin带你飞 专题六 最小生成树J - Borg Maze

题意

题目好难懂啊，英文题读起来好痛苦。
大概意思就是，给定一起点，和n个点有外星人，你有一个搜索集团，让你去同化这些外星人。在起点和每同化一个外星人时，该集团可能会分裂成两个或两个以上的组织(但他们的意识仍然是集体)。搜索迷宫的成本是一共所走过的总距离。
求最小的成本是多少。

思路

因为只能在起点和外星人所在点进行分裂，那么这些点可看做结点，任意两点间的距离看做边权值，则显然是一个最小生成树问题。将A和S点的坐标提取出来，通过bfs，计算任意两点之间的距离，然后prim即可。
另外，此题数据较坑。提交时无辜的wrong了好几次。输入数据每行的最后面都有一个空格，要注意gets()处理。

代码

//
//  main.cpp
//  demo
//
//  Created by shiyi－mac on 16/1/2.
//  Copyright © 2016年 shiyi－mac. All rights reserved.
//
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

const int N = 109;
const int MAX = 1000000;
int g[N][N];
int d[N];
char s[59][59];
int qx[] = {-1, 1, 0, 0};
int qy[] = {0, 0, 1, -1};
bool vist[59][59];

struct Node
{
    int x, y, num;
}spot[N];

int find(int x, int y, int len)
{
    for(int i=0;i<len;i++)
        if(spot[i].x == x && spot[i].y == y)
            return i;
    return -1;
}

void bfs(int pos, int x, int y, int xlen, int ylen, int plen)
{
    queue<Node> q;
    spot[pos].num = 0;
    q.push(spot[pos]);
    vist[x][y] = 1;
    while(!q.empty())
    {
        Node t = q.front();
        q.pop();
        if(s[t.x][t.y] == 'A' || s[t.x][t.y] == 'S')
        {
            int tpos = find(t.x, t.y, plen);
            g[pos][tpos] = g[tpos][pos] = t.num;
        }

        int dx, dy;
        for(int i=0;i<4;i++)
        {
            dx = qx[i] + t.x;
            dy = qy[i] + t.y;
            if(dx>=0 && dx<xlen && dy>=0 && dy<ylen
               && !vist[dx][dy] && s[dx][dy]!='#')
            {
                Node p = {dx, dy, t.num+1};
                q.push(p);
                vist[dx][dy] = 1;
            }
        }
    }
}

int prim(int n)
{
    for(int i=0;i<n;i++)
        d[i] = g[0][i];
    d[0] = -1;

    int ans = 0;

    for(int i=1;i<n;i++)
    {
        int min = MAX;
        int imin = -1;
        for(int j=0;j<n;j++)
            if(d[j]!=-1 && min > d[j])
                min = d[j], imin = j;

        ans += min;
        d[imin] = -1;
        for(int j=0;j<n;j++)
            if(d[j]!=-1 && d[j] > g[imin][j])
                d[j] = g[imin][j];
    }
    return ans;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int y, x;
        int num = 0;
        scanf("%d%d", &y, &x);
        gets(s[0]);
        for(int i=0;i<x;i++)
            gets(s[i]);
        for(int i=0;i<x;i++)
        {
            for(int j=0;j<y;j++)
                if(s[i][j] == 'A' || s[i][j] == 'S')
                    spot[num++] = {i, j};
        }

        for(int i=0;i<num;i++)
        {
            memset(vist, 0, sizeof(vist));
            s[spot[i].x][spot[i].y] = ' ';
            bfs(i, spot[i].x, spot[i].y, x, y, num);
        }
        printf("%d\n",prim(num));
    }
    return 0;
}