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

题目地址：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