poj 3026 Borg Maze bfs建圖+最小生成樹

題目說從S開始，在S或者A的地方可以分裂前進。 想一想後發現就是求一顆最小生成樹。

首先bfs預處理得到每兩點之間的距離，我的程序用map做了一個映射，將每個點的坐標映射到1-n上，這樣建圖比較方便。

然後一遍prime就夠了。注意用gets（）讀入地圖的時候，上面還要用一個gets（）接住無用的空格。。（為啥不用getchar？0 0，看了討論版才知道，

因為空格很多………………）

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
char map1[55][55];
int head,tail;
int x,y;
map<int,int> M;
struct node
{
    int x,y;
    int dis;
}q[100000];
int top;
int start;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int dis[150][150];
bool vis[150][150];
void bfs(int k,int st)
{
    memset(vis,0,sizeof(vis));
    head=tail=0;
    node tmp,tt;
    tmp.x=st/x;
    tmp.y=st%x;
    vis[tmp.x][tmp.y]=1;
    tmp.dis=0;
    int tot=0;
    q[tail++]=tmp;
    int f;
    while(head<tail)
    {
        tmp=q[head];
        for(int d=0;d<4;d++)
        {
            tt=tmp;
            tt.x+=dx[d];
            tt.y+=dy[d];
            tt.dis++;
            if(map1[tt.x][tt.y]!='#'&&!vis[tt.x][tt.y])
            {
                vis[tt.x][tt.y]=1;
                if(f=M[tt.x*x+tt.y])
                {
                    tot++;
                    dis[k][f]=tt.dis;
                }
                q[tail++]=tt;
                if(tot==top) return;
            }
        }
        head++;
    }
}
int n,sum;
int visit[150],d[150];
void prime(int n)
{
	int i,j,min,v;
	sum=0;
	for(i=1;i<=n;i++)
	{
		d[i]=dis[1][i];
		visit[i]=0;
	}
	visit[1]=1;
	for(i=1;i<n;i++)
	{
		min=INF;
		v=1;
		for(j=1;j<=n;j++)
		{
			if(!visit[j]&&min>d[j])
			{
				min=d[j];
				v=j;
			}
		}
		sum+=min;
		visit[v]=1;
		for(j=1;j<=n;j++)
		{
			if(!visit[j]&&dis[v][j]<d[j])
				d[j]=dis[v][j];
		}
	}
}
int main()
{
    char tmp[1000];
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        memset(dis,0x3f,sizeof(dis));
        M.clear();
        top=0;
        scanf("%d%d",&x,&y); gets(tmp);//接住空格
        for(int i=0;i<y;i++){
            gets(map1[i]);
        }
        for(int i=1;i<y-1;i++)
        {
            for(int j=1;map1[i][j];j++)
            {
                if(map1[i][j]=='A'||map1[i][j]=='S')
                {
                    top++;
                    if(map1[i][j]=='S') start=top;
                    M[i*x+j]=top;
                    dis[top][top]=0;

                }
            }
        }
        for(int i=1;i<y-1;i++)
        {
            for(int j=1;map1[i][j];j++)
            {
                if(map1[i][j]=='A'||map1[i][j]=='S')
                {
                    bfs(M[i*x+j],i*x+j);
                }
            }
        }
        prime(top);
        printf("%d\n",sum);
    }
    return 0;
}