Borg Maze （bfs ，最小生成树）

#include <stdio.h>
#include <string.h>
#include <queue>
#define  N 105
#define  INF 1000000000
using namespace std;
structnode
{
    int x,y;
};
node dir[4]={{-1,0},{1,0},{0,1},{0,-1}} ;
int p[N][N],maps[N][N],visit[N][N],value[N][N],n,m,num;
void bfs(int x,int y)     
{
    queue<node>Q;
    node t,u,v;
    int xi,yi,i;
    t.x=x;
    t.y=y;
    memset(visit,0,sizeof(visit));
    value[x][y]=0;
    Q.push(t);
    visit[x][y]=1;
    while (!Q.empty())
    {
        u=Q.front();
        Q.pop();
        if (p[u.x][u.y])
            maps[p[x][y]][p[u.x][u.y]]=value[u.x][u.y];
        for (i=0;i<4;i++)
        {
            xi=u.x+dir[i].x;
            yi=u.y+dir[i].y;
            if (xi>0 && xi<=m && yi>0 && yi<=n && !visit[xi][yi] && p[xi][yi]>=0)
            {
                visit[xi][yi]=1;
                value[xi][yi]=value[u.x][u.y]+1;
                v.x=xi;
                v.y=yi;
                Q.push(v);
            }
        }
    }
}
int prim()    
{
    int dist[N],vis[N],minn,i,j,pos,sum = 0;
    for (i=1;i<num;i++)
    {
        dist[i]=maps[1][i];
        vis[i]=0;
    }
    vis[1]=1;
    for (i=1;i<num-1;i++)
    {
        minn=INF;
        for(j=1;j<num;j++)
            if ( !vis[j] && dist[j]<minn )
            {
                minn=dist[j];
                pos=j;
            }
        vis[pos]=1;
        sum+=minn;
        for(j=1;j<num;j++)
            if(!vis[j] && dist[j]>maps[pos][j])
            dist[j]=maps[pos][j];
    }
    return sum;
}
int main()
{
    int T,i,j;
    char str[N] ;
    scanf("%d",&T);
    while (T--)
    {
        scanf ("%d%d",&m,&n);
        gets(str);
        memset(p,0,sizeof(p));
        num=1;
        for(i=1;i<=n;i++)
        {
            gets(str);
            for(j=1;j<=m;j++)
            {
                if(str[j-1]==‘#‘)
                p[i][j]=-1;
                else if(str[j-1]==‘A‘ || str[j-1]==‘S‘)
                p[i][j]=num++;
            }
        }
        for (i=1;i<=n;i++)
            for (j=1;j<=m;j++)
                if(p[i][j]>0)
                bfs(i,j);
        printf ("%d\n",prim());
    }
    return 0 ;
}

Borg Maze （bfs ，最小生成树）

原文：http://www.cnblogs.com/You-Change/p/3518110.html