杭电1242Rescue题(bfs+优先队列)

题目链接~~>

这题是学习优先队列的第一题搞了好久才AC：

先介绍一下优先队列：

头文件：

  

   

    

     

    
    

     
 #include<queue> 
     
    
   

    

     

    
    

     
 using namespace std;
     
    
  
 

由大到小出队：

  

   

    

     

    
    

     
 struct zhang
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int x,y;
     
    
   

    

     

    
    

     
 friend bool operator<(const zhang &a,const zhang &b)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 return a.x < b.x ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       };
     
    
   

    

     

    
    

     
 priority_queue<zhang>q;
     
    
   

    

     

    
    

     

       zhang current;
     
    
  
 

由小到大出队：
           将上面的 return a .x < b.x ;中的 "<" 改为 “>” ；但传说中这种方法G++编译器编译不过；

（非本人）代码：

 

   

    

     

      

     
     

      

       #include <iostream>
      
     
    

     

      

     
     

      

       #include <stdio.h>
      
     
    

     

      

     
     

      

       #include <string.h>
      
     
    

     

      

     
     

      

       #include <queue>
      
     
    

     

      

     
     

      

       #define N 201
      
     
    

     

      

     
     

      

       using namespace std;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       //优先队列解决,广度优先
      
     
    

     

      

     
     

      

       struct Persion
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      
 int x,y;
      
     
    

     

      

     
     

      
 int time;
      
     
    

     

      

     
     

      
 friend bool operator < (const Persion &a,const Persion &b)
      
     
    

     

      

     
     

      

        {
      
     
    

     

      

     
     

      
 return a.time>b.time; //">" 返回队列中较小的元素；"< " 则返回队列中较大的元素
      
     
    

     

      

     
     

      

        }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       };
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
      
     
    

     

      

     
     

      

       char map[N][N];
      
     
    

     

      

     
     

      

       int visited[N][N];
      
     
    

     

      

     
     

      

       int m,n;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       int BFS(int x,int y)
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 priority_queue <Persion>q;
      
     
    

     

      

     
     

      

        Persion current,next;
      
     
    

     

      

     
     

      
 memset(visited,0,sizeof(visited));
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

        current.x=x;
      
     
    

     

      

     
     

      

        current.y=y;
      
     
    

     

      

     
     

      

        current.time=0;
      
     
    

     

      

     
     

      

        visited[current.x][current.y]=1;
      
     
    

     

      

     
     

      

        q.push(current);
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 while(!q.empty())
      
     
    

     

      

     
     

      

        {
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

        current=q.top();
      
     
    

     

      

     
     

      

        q.pop();
      
     
    

     

      

     
     

      
 for(int i=0;i<4;i++)
      
     
    

     

      

     
     

      

        {
      
     
    

     

      

     
     

      

        next.x=current.x+dir[i][0];
      
     
    

     

      

     
     

      

        next.y=current.y+dir[i][1];
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&map[next.x][next.y]!='#'&&!visited[next.x][next.y])
      
     
    

     

      

     
     

      

        {
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 if(map[next.x][next.y]=='r')
      
     
    

     

      

     
     

      
 return current.time+1;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 if(map[next.x][next.y]=='x')
      
     
    

     

      

     
     

      

        next.time=current.time+2;
      
     
    

     

      

     
     

      
 else
      
     
    

     

      

     
     

      

        next.time=current.time+1;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

        visited[next.x][next.y]=1;
      
     
    

     

      

     
     

      

        q.push(next);
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

        }
      
     
    

     

      

     
     

      

        }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

        }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 return -1;
      
     
    

     

      

     
     

      

       }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       int main()
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 int i,j;
      
     
    

     

      

     
     

      

        Persion angle;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 while(cin>>n>>m&&(m||n))
      
     
    

     

      

     
     

      

        {
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 for(i=0;i<n;i++)
      
     
    

     

      

     
     

      
 for(j=0;j<m;j++)
      
     
    

     

      

     
     

      

        {
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 cin>>map[i][j];
      
     
    

     

      

     
     

      
 if(map[i][j]=='a')
      
     
    

     

      

     
     

      

        {
      
     
    

     

      

     
     

      

        angle.x=i;
      
     
    

     

      

     
     

      

        angle.y=j;
      
     
    

     

      

     
     

      

        }
      
     
    

     

      

     
     

      

        }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 int time=BFS(angle.x,angle.y);
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 if(time==-1)
      
     
    

     

      

     
     

      
 cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
      
     
    

     

      

     
     

      
 else
      
     
    

     

      

     
     

      
 cout<<time<<endl;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

        }
      
     
    

     

      

     
     

      
 return 0;
      
     
    

     

      

     
     

      

       }
      
     
   


 




 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/9154235