POJ 3026 Borg Maze(BFS+최소 생 성 트 리)

제목 링크:http://poj.org/problem?id=3026
이 문 제 는 S 와 A 를 같은 점 으로 볼 수 있다.최소 생 성 트 리 의 성질 에 따라 출발점 이 어디 에 있 든 같 기 때문이다.그리고 각 지점 에서 나머지 지점 까지 의 거 리 는 BFS 로 검색 할 수 있 으 며 검색 과정 에서 거 리 를 행렬 로 저장 합 니 다.그리고 모든 거 리 를 얻 은 후에 prim 알고리즘 으로 최소 생 성 트 리 를 구 합 니 다.
코드 는 다음 과 같 습 니 다:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include<algorithm>

using namespace std;
int n, m, a[60][60], map[110][110], d[110], vis1[110][110], vis[110], maxint=100000, num;
char st[60][60];
int jx[]={0,0,1,-1};
int jy[]={1,-1,0,0};
struct node
{
    int x, y, ans;
}fei[10000000];
void bfs(int x, int y, int q)
{
    int i, j, s=0, e=0, xx=0;
    node f1, f2;
    f1.x=x;
    f1.y=y;
    f1.ans=0;
    fei[s++]=f1;
    vis1[x][y]=1;
    while(s>e)
    {
        f1=fei[e++];
        if(a[f1.x][f1.y]!=0&&a[f1.x][f1.y]!=q)
        {
            map[q][a[f1.x][f1.y]]=map[a[f1.x][f1.y]][q]=f1.ans;
            xx++;
            if(xx==num-1)
            {
                return ;
            }
        }
        for(i=0;i<4;i++)
        {
            f2.x=f1.x+jx[i];
            f2.y=f1.y+jy[i];
            if(f2.x>=0&&f2.x<n&&f2.y>=0&&f2.y<m&&!vis1[f2.x][f2.y]&&(st[f1.x][f1.y]=='A'||st[f1.x][f1.y]=='S'||st[f1.x][f1.y]==' '))
               {
                   vis1[f2.x][f2.y]=1;
                   f2.ans=f1.ans+1;
                   fei[s++]=f2;
               }
        }
    }
    return ;
}
void prim()
{
    int ans=0, i, j, pos, min1;
    for(i=2;i<=num;i++)
    {
        d[i]=map[1][i];
    }
    vis[1]=1;
    for(i=1;i<num;i++)
    {
        min1=maxint;
        for(j=2;j<=num;j++)
        {
            if(!vis[j]&&min1>d[j])
            {
                min1=d[j];
                pos=j;
            }
        }
        vis[pos]=1;
        ans+=min1;
        for(j=2;j<=num;j++)
        {
            if(!vis[j]&&d[j]>map[pos][j])
            {
                d[j]=map[pos][j];
            }
        }
    }
    printf("%d
",ans);
}
int main()
{
    int t, i, j, k, p, q;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d ",&m,&n);
        k=1;
        memset(a,0,sizeof(a));
        memset(vis,0,sizeof(vis));
        num=0;
        for(i=0; i<n; i++)
        {
            gets(st[i]);
            for(j=0; j<m; j++)
            {
                if(st[i][j]=='A'||st[i][j]=='S')
                {
                    a[i][j]=k++;
                    num++;
                }
            }
        }
        for(i=1;i<=num;i++)
        {
            for(j=1;j<=num;j++)
            {
                map[i][j]=maxint;
            }
        }
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                if(a[i][j])
                {
                    memset(vis1,0,sizeof(vis1));
                    q=a[i][j];
                    bfs(i,j,q);
                }
            }
        }
        prim();
    }
    return 0;
}