hdu 1242 Rescue(BFS,优先队列,基础)

题目

 

/******************以下思路来自百度菜鸟的程序人生*********************/

  bfs即可,可能有多个’r’,而’a’只有一个,从’a’开始搜,找到的第一个’r’即为所求

  需要注意的是这题宽搜时存在障碍物,遇到’x’点是,时间+2,如果用普通的队列就

并不能保证每次出队的是时间最小的元素,所以要用优先队列,第一次用优先队列,还不熟练哇

  优先队列(priority_queue)的基本操作:

  empty(); 队列为空返回1

  pop();   出队

  push();  入队

  top();   返回队列中优先级最高的元素

  size();  返回队列中元素的个数

/**************************************************************/

 

修改了学妹的代码,增加了优先队列,成功AC~

 

hdu 1242 Rescue(BFS,优先队列,基础)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
char map[205][205];
bool visit[205][205];
int xx[5]={1,-1,0,0};
int yy[5]={0,0,1,-1};
int n,m,x,y;
struct node
{
    int x,y;
    int time;
    friend bool operator < (const node &a,const node &b)
    {
        return a.time>b.time;
    }
};
void bfs(int &min)
{
    priority_queue<node>q;
    int i;
    node step,temp;
    step.x=x;
    step.y=y;
    step.time=0;
    visit[x][y]=true;
    q.push(step);
    while(!q.empty())
    {
        step=q.top();
        q.pop();
        if(map[step.x][step.y]==r)
        {
            min=step.time;
            return ;
        }
        else if(map[step.x][step.y]!=r)
        {
            for(i=0;i<4;i++)
            {
                
                if(map[step.x+xx[i]][step.y+yy[i]]!=# && !visit[step.x+xx[i]][step.y+yy[i]])
                {
                    if(map[step.x+xx[i]][step.y+yy[i]]==x)
                    {
                        temp.x=step.x+xx[i];
                        temp.y=step.y+yy[i];
                        
                        temp.time=step.time+2;
                    }
                    else
                    {
                        temp.x=step.x+xx[i];
                        temp.y=step.y+yy[i];
                        temp.time=step.time+1;
                    }
                    visit[temp.x][temp.y]=true;
                    q.push(temp);
                }
            }
        }
    }
}
int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        int i,j;
        int min=50000;
        memset(visit,false,sizeof(visit));
        for(i=0;i<=n+1;++i)
            map[i][0]=map[i][m+1]=#;
        for(i=0;i<=m+1;++i)
            map[0][i]=map[n+1][i]=#;
        for(i=1;i<=n;++i)
        {
            for(j=1;j<=m;j++)
            {
                cin>>map[i][j];
                if(map[i][j]==a)
                {
                    x=i;
                    y=j;
                }
            }
        }
        bfs(min);
        if(min<50000)
            printf("%d\n",min);
        else
            printf("Poor ANGEL has to stay in the * all his life.\n");
    }
    return 0;
}
View Code

hdu 1242 Rescue(BFS,优先队列,基础)

上一篇:SVN源码服务器搭建-详细教程


下一篇:[USACO精选] 第二章 动态规划(一)