poj 3206 Borg Maze MST

    很无聊的题目，先bfs求下最短，再prim，输入还有多余空格……懒得敲了，随便找了个代码。

以下代码从http://hi.baidu.com/00gfzs/item/6dd7bf221b955c404799624a转载

#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
using namespace std;
int Val[102];
//prim记录最优值
bool PR[102];
//prim标记是否走过
int move[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};
//北西南东
struct IN
{
    int x,y;
}
Alien[102];
//表示外星人和s起始点
struct Position
{
    int x;
    int y;
    int step;
};
//bfs定位点
int map[52][52];
//记录输入地形
bool M[52][52];
//标记50*50矩阵
int A[102][102];
//生成连接矩阵
int x,y,num;
//x行y列
void bfs(int pos)
{
    memset(M,true,sizeof(M));
    queue<Position> Q;
    Position here,next;
    here.x = Alien[pos].x;
    here.y = Alien[pos].y;
    here.step = 0;
    Q.push(here);
    M[here.x][here.y] = false;
    int Find = 0;
    while(!Q.empty())
    {
        if (Find == num - 1)
        break;
        int i;
        int xx,yy;
        here = Q.front();
        Q.pop();
        for(i=0; i<4; i++)
        {
            xx = here.x + move[i][0];
            yy = here.y + move[i][1];
            if(xx>=0&&xx<x&&yy>=0&&yy<y&&map[xx][yy]!= -2&&M[xx][yy])
            {
                next.x = xx;
                next.y = yy;
                next.step = here.step +1;
                Q.push(next);
                M[xx][yy] = false;
                if(map[xx][yy]!=-1)
                {
                    A[pos][map[xx][yy]] = A[map[xx][yy]][pos] = next.step;
                    Find++;
                }
            }
        }
    }
}
int main()
{
    int n;
    cin>>n;
    char tmp[300];
    while(n--)
    {
        cin>>y>>x;
        int i,j,k;
        num = 0;
        gets(tmp);
        //处理x，y后面空格
        for(i=0; i<x; i++)
        {
            gets(tmp);
            for(j=0; j<y; j++)
            {
                if(tmp[j]=='A'||tmp[j]=='S')
                {
                    Alien[num].x = i;
                    Alien[num].y = j;
                    map[i][j] = num;
                    num++;
                }

                else
                {
                    if (tmp[j] == '#')
                    map[i][j] = -2;
                    //表示#
                    else map[i][j] = -1;
                    //表示空格
                }
                }
        }
        memset(A,0,sizeof(A));
        for(i=0; i<num-1; i++)
        bfs(i);
        memset(PR,true,sizeof(PR));
        for(i=1; i<num; i++)
        Val[i] = A[0][i];
        PR[0] = false;
        int sum = 0;
        int Mmin,temp;
        for(i=1; i<num; i++)
        {
            Mmin = 0xffffff;
            for(j=1; j<num; j++)
            {
                if(Val[j]<Mmin&&PR[j])
                {
                    Mmin = Val[j];
                    temp = j;
                }
            }
            sum += Mmin;
            PR[temp] = false;
            for(k=1; k<num; k++)
            if(PR[k]&&Val[k]>A[temp][k])
            Val[k] = A[temp][k];
        }
        cout<<sum<<endl;
    }
    return 0;
}