Borg Maze poj3026

首先这道题不得不让我吐槽下，测试数据太无语了，在输入列和行后，后面竟然还会输空格，所以不能用getchar（）去处理'\n'，只能用gets（），这样一次性就可以处理掉空格和'\n'。

然后再说说本题的思想吧，我是先对每个A或S用一次BFS，求出它与其它的A或S的最短距离，然后再以这些A或S建图，求一次最小生成树，然后把所有的边权相加

[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct st
{
    int x,y,step;
}w,tmp;
st q[2505];
const int INF=100000000;
int map[55][55];
bool visit[55][55];
bool visit1[105];
int dist[105][105];
int dirt[4][2]={0,1,0,-1,1,0,-1,0};
int d[105];
int t,n,m,num;

bool ok(int x,int y)
{
    return x>=0&&x<n&&y>=0&&y<m&&map[x][y]!=-1;
}

void BFS(int u)
{
    memset(visit,false,sizeof(visit));
    visit[w.x][w.y]=true;
    int front=0,rear=0;
    q[rear++]=w;
    while(front<rear)
    {
        w=q[front++];
        if(map[w.x][w.y]>0)
            dist[u][map[w.x][w.y]]=w.step;
        for(int i=0;i<4;i++)
        {
            tmp.x=w.x+dirt[i][0];
            tmp.y=w.y+dirt[i][1];
            tmp.step=w.step+1;
            if(ok(tmp.x,tmp.y)&&!visit[tmp.x][tmp.y])
            {
                visit[tmp.x][tmp.y]=true;
                q[rear++]=tmp;
            }
        }
    }
}

int main()
{
    int i,j,k,sum;
    scanf("%d",&t);
    char tmp[100];
    while(t--)
    {
        num=0;
        scanf("%d%d",&m,&n);
        //getchar();
        gets(tmp);
        for(i=0;i<n;i++)
        {
            gets(tmp);
            for(j=0;j<m;j++)
            {
                if(tmp[j]=='S'||tmp[j]=='A')
                    map[i][j]=++num;
                else if(tmp[j]==' ')
                    map[i][j]=0;
                else
                    map[i][j]=-1;
            }
        }
        //计算任意两个alien的最短距离
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
                if(map[i][j]>0)
                {
                    w.x=i;w.y=j;w.step=0;
                    BFS(map[i][j]);
                }

        //Prim
        for(i=0;i<=num;i++)
        {
            visit1[i]=false;
            d[i]=INF;
        }
        d[1]=0;
        for(i=1;i<=num;i++)
        {
            k=0;
            for(j=1;j<=num;j++)
                if(d[j]<d[k]&&!visit1[j])
                    k=j;
            if(k==0)
                break;
            visit1[k]=true;
            for(j=1;j<=num;j++)
                if(!visit1[j]&&dist[k][j]<d[j])
                    d[j]=dist[k][j];
        }
        sum=0;
        for(j=1;j<=num;j++)
            sum+=d[j];
        printf("%d\n",sum);
    }
    return 0;
}

补充：软件开发 , C++ ,