首页 > > 程序设计 > C/C++ >

POJ 3026 Borg Maze 广搜(BFS)+最小生成树

2018-06-17 23:55:55来源：未知阅读 ()

题意：从S出发，去抓每一个A，求总路径最短长度。在S点和A点人可以分身成2人，不过一次只能让一个人走。

思路是先利用BFS求出各点之间的距离，建成图，再套用最小生成树模板。

一次性A了。不过觉得在判断第几个编号的点时稍显麻烦了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int inf=1000000;
const int maxn=205;
char mapp[maxn][maxn];
bool visit[maxn][maxn];
bool vis[maxn];
int dx[]= {-1,0,1,0}; //四个方向
int dy[]= {0,-1,0,1};
int mat[maxn][maxn],dis[maxn];
int cou,ans;

struct Node
{
    int x;
    int y;
    int s; //记录距离
    int num; //点的编号
} next,nodes[maxn]; //nodes[]存所有的点
void bfs(Node node,int a)
{
    memset(visit,0,sizeof(visit));
    node.s=0;
    mapp[node.y][node.x]=' '; //访问过后将'S'或'A'变成' '，下次不需重复访问
    queue<Node>q;
    visit[node.x][node.y]=true;
    q.push(node);
    while(!q.empty())
    {
        node=q.front();
        if(mapp[node.y][node.x]=='A')
        {
            if(a==0)
            {
                nodes[cou]=node;
                mat[a][cou]=mat[cou][a]=node.s;
                cou++; //记录有多少个点
            }
            else
            {
                int b;
                for(int j=0;; j++)
                    if(nodes[j].x==node.x && nodes[j].y==node.y)
                    {
                        b=nodes[j].num;
                        break;
                    }
                mat[a][b]=mat[b][a]=node.s; //将距离写入对角矩阵
            }
        }
        q.pop();
        for(int i=0; i<4; i++)
        {
            next=node;
            next.x=node.x+dx[i];
            next.y=node.y+dy[i];
            if(!visit[next.x][next.y] && (mapp[next.y][next.x]==' ' || mapp[next.y][next.x]=='A'))
            {
                visit[next.x][next.y]=true;
                next.s=node.s+1;
                q.push(next);

            }
        }
    }
    return ;
}
bool prim()
{
    memset(vis,0,sizeof(vis));
    for(int i=0;i<cou;i++)
        dis[i]=(i==0? 0:inf);
    ans=0;
    for(int i=0;i<cou;i++)
    {
        int temp=inf,k=0;
        for(int j=0;j<cou;j++)
        {
            if(!vis[j] && dis[j]<temp )
            {
                temp=dis[j];
                k=j;
            }
        }
        if(temp==inf)
            return false;
        vis[k]=true;
        ans+=temp;
        for(int j=0;j<cou;j++)
        {
            if(!vis[j] && dis[j]>mat[k][j])
                dis[j]=mat[k][j];
        }
    }
    return true;
}
int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int x,y;
        memset(mapp,0,sizeof(mapp));
        scanf("%d%d",&x,&y);
        char c[maxn]={0};
        gets(c);
        for(int i=0; i<y; i++)
            gets(mapp[i]);
        for(int i=0; i<x; i++)
            for(int j=0; j<y; j++)
                if(mapp[i][j]=='S')
                {
                    nodes[0].y=i;
                    nodes[0].x=j;
                }
        bool flag=true;
        cou=1;
        for(int i=0; i<cou; i++)
        {
            bfs(nodes[i],i);
            if(flag)
            {
                for(int j=0; j<cou; j++)
                    nodes[j].num=j; //给各个点编号，只运行一次
                flag=false;
            }
        }
        prim();
        printf("%d\n",ans);
    }
    return 0;
}