poj3026Borg Maze（bfs预处理+最小生成树）

Description

Input

Output

Sample Input

2
6 5
##### 
#A#A##
# # A#
#S  ##
##### 
7 7
#####  
#AAA###
#    A#
# S ###
#     #
#AAA###
#####  

Sample Output

8
11

Source

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=60*60;
int root[maxn],dis[maxn][maxn],map[maxn][maxn],d[maxn];
int gra[maxn][maxn];
bool vis[maxn][maxn],hash[maxn];

int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int n,m,t,cal;

struct Point
{
    int x,y;
}point[maxn];


bool check(int x,int y)
{
    if(x>=1&&x<=n&&y>=1&&y<=m&&!vis[x][y]&&map[x][y]>=0)
        return true;
    return false;
}

void prim()
{
    memset(hash,false,sizeof(hash));
    int now,tmp,ans=0;
    memset(d,INF,sizeof(d));
    d[1]=0;
    for(int i=1;i<=cal;i++)
    {
        tmp=INF;
        for(int j=1;j<=cal;j++)
        {
            if(!hash[j]&&tmp>d[j])
            {
                tmp=d[j];
                now=j;
            }
        }
        ans=ans+tmp;
        hash[now]=true;
        for(int j=1;j<=cal;j++)
        {
            if(!hash[j]&&d[j]>gra[now][j])
                d[j]=gra[now][j];
        }
    }
    cout<<ans<<endl;
}

void bfs(int sx,int sy)
{
    memset(dis,INF,sizeof(dis));
    memset(vis,false,sizeof(vis));
    queue<Point>Q;
    while(!Q.empty())  Q.pop();
    Point current,next;
    current.x=sx;
    current.y=sy;
    vis[sx][sy]=true;
    dis[sx][sy]=0;
    Q.push(current);
    while(!Q.empty())
    {
        current=Q.front();
        Q.pop();
        for(int i=0;i<4;i++)
        {
            next.x=current.x+dx[i];
            next.y=current.y+dy[i];
            if(check(next.x,next.y)&&dis[next.x][next.y]>dis[current.x][current.y]+1)
            {
                dis[next.x][next.y]=dis[current.x][current.y]+1;
                if(map[next.x][next.y]>=1)
                {
                    gra[map[next.x][next.y]][map[sx][sy]]=dis[next.x][next.y];
                    gra[map[sx][sy]][map[next.x][next.y]]=dis[next.x][next.y];
                }
                vis[next.x][next.y]=true;
                Q.push(next);
            }
        }
    }
}


void solve()
{
     for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
         if(map[i][j]>0)
             bfs(i,j);
     prim();
}

int main()
{
    scanf("%d",&t);
    char str[maxn];
    while(t--)
    {
        cal=1;
        scanf("%d%d",&m,&n);
        gets(str);
        for(int i=1;i<=n;i++)
        {
            gets(str+1);
            for(int j=1;j<=m;j++)
            {
               if(str[j]=='#')  map[i][j]=-1;
               if(str[j]=='S')  map[i][j]=1;
               if(str[j]=='A')  map[i][j]=++cal;
               if(str[j]==' ')  map[i][j]=0;
            }
        }
        solve();
    }
    return 0;
}