HDU 1242 Rescue(优先队列+bfs） - c++编程基础

TOP

HDU 1242 Rescue(优先队列+bfs）

2015-07-20 18:00:33 来源: 作者: 【大中小】浏览:1次

题目地址：HDU 1242

这个题相比于普通的bfs有个特殊的地方，经过士兵时会额外消耗时间，也就是说此时最先搜到的时候不一定是用时最短的了。需要全部搜一遍才可以。这时候优先队列的好处就显现出来了。利用优先队列，可以让队列中的元素按时间排序，让先出来的总是时间短的，这样的话，最先搜到的一定是时间短的，就不用全部搜一遍了。PS：我是为了学优先队列做的这题。。不是为了这题而现学的优先队列。。

代码如下；

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include
          
            using namespace std; int vis[300][300], n, m; char mp[300][300]; int jx[]={0,0,1,-1}; int jy[]={1,-1,0,0}; struct node { int x, y, ans; bool operator<(const node &a) const{ return ans>a.ans; } }; void bfs(int x, int y) { memset(vis,0,sizeof(vis)); priority_queue
           
            q; node f1, f2; f1.x=x; f1.y=y; f1.ans=0; q.push(f1); vis[x][y]=1; while(!q.empty()) { f1=q.top(); q.pop(); if(mp[f1.x][f1.y]=='r') { printf("%d\n",f1.ans); return ; } for(int i=0;i<4;i++) { f2.x=f1.x+jx[i]; f2.y=f1.y+jy[i]; if(f2.x>=0&&f2.x
            
             =0&&f2.y


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU 4902 线段树\|\|暴力	下一篇：纠结的CLI C++与Native C++的交互

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: