hdu 1242Rescue（bfs+优先队列）

51 阅读 0 评论 34 点赞

我是靠谱客的博主矮小项链，最近开发中收集的这篇文章主要介绍hdu 1242Rescue（bfs+优先队列），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这个题还没有敲稍微看了一下别人的代码

觉得这个题太好了，特别有意思

题意就是给一个矩阵有强有敌人有angel 有friends

friends可能有多个但是hdu一个就能水过

我们还是按照正确的解法来考虑

r要到达a 中间可能会遇到x x是敌人需要1单位时间去消灭

我们要求出最少的时间使得a被营救

那么r如果经过某一个点消灭了一个敌人就会有额外的时间

这样队列中我们就不能只依靠顺序来bfs 了而是依靠用时最少来bfs

但是多个r怎么解决？

这个逆向思维一下从a出发看先遇到哪个r

这样下来这个思路就清楚了

开始敲

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

const int maxn=205;
char map[maxn][maxn];
bool vis[maxn][maxn];
int n,m;
int xpos,ypos;//记录a的位置 也就是起点
int dir[4][2]={-1,0,1,0,0,-1,0,1};


struct Node
{
    int x,y,time;
    bool operator <(const Node & n)const
    {
        return time>n.time;
    }
};

int bfs()
{
    int i;
    memset(vis,0,sizeof(vis));
    Node node,no;
    priority_queue<Node> pq;
    node.x=xpos;
    node.y=ypos;
    node.time=0;
    pq.push(node);
    vis[node.x][node.y]=1;
    while(!pq.empty())
    {
        node=pq.top();
        pq.pop();
        //printf("tanchuyici %d %dn",node.x,node.y);

        if(map[node.x][node.y]=='r')
        return node.time;

        for(i=0;i<4;++i)
        {
            no.x=node.x+dir[i][0];
            no.y=node.y+dir[i][1];
            if(vis[no.x][no.y]==0 && no.x>=0 && no.x<n && no.y>=0 &&no.y<m && map[no.x][no.y]!='#')
            {
                if(map[no.x][no.y]=='x')
                no.time=node.time+2;
                else
                no.time=node.time+1;
                vis[no.x][no.y]=1;
                pq.push(no);
            }
        }
    }
    return -1;
}

int main()
{
    int i,j,ans;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        getchar();
        for(i=0;i<n;++i)
        {
            for(j=0;j<m;++j)
            {
                scanf("%c",&map[i][j]);
                if(map[i][j]=='a')
                {
                    xpos=i;
                    ypos=j;
                }
            }
            getchar();
        }
        ans=bfs();
        if(ans==-1)
        printf("Poor ANGEL has to stay in the prison all his life.n");
        else
        printf("%dn",ans);
    }
    return 0;
}