优先队列笔记

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
char a[201][201];
bool isv[201][201];        //记录访问过没有 
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int N,M;
int sx,sy,ex,ey;
struct NODE{
    int x;
    int y;
    int step;
    friend bool operator < (NODE n1,NODE n2)    //自定义优先级。在优先队列中，优先级高的元素先出队列。 
    {
        return n1.step > n2.step;    //通过题意可知 step 小的优先级高，需要先出队。
    }
}; 
bool judge(int x,int y)
{
    if( x<1 || y<1 || x>N || y>M )
        return 1;
    if( isv[x][y] )
        return 1;
    if( a[x][y]=='#' )
        return 1;
    return 0;
}
int bfs()    //返回从（x，y）开始广搜，到右下角的最短步数，如果无法到达右下角，返回0 
{
    memset(isv,0,sizeof(isv));
    priority_queue <NODE> q;    //定义一个优先队列 
    NODE cur,next;
    cur.x = sx;
    cur.y = sy;
    cur.step = 0;
    isv[sx][sy] = true;
    q.push(cur);    //第一个元素入队 
    while(!q.empty()){
        cur = q.top();    //队首出队，注意不是front() 
        q.pop();
        if(cur.x==ex && cur.y==ey)    //到终点
            return cur.step; 
        for(int i=0;i<4;i++){
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            if( judge(nx,ny) )    //判定 
                continue;
            //可以走
            next.x = nx;
            next.y = ny;
            if(a[nx][ny]=='x')
                next.step = cur.step + 2;
            else 
                next.step = cur.step + 1;
            isv[nx][ny] = true;
            q.push(next);
        }
    }
    return -1;
}
int main()
{
    while(cin>>N>>M){
        for(int i=1;i<=N;i++)    //输入
            for(int j=1;j<=M;j++){
                cin>>a[i][j];
                if(a[i][j]=='a')
                    ex=i,ey=j;
                else if(a[i][j]=='r')
                    sx=i,sy=j;
            }
        int step = bfs();
        if(step==-1)    //不能到达
            cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
        else
            cout<<step<<endl;
    }
    return 0;
}


/*
*优先队列实际应用 
*/
/*#include<cstdio>
#include<queue>
using namespace std;
struct node
{
    int x,y;
    bool operator < (const node & a) const
    {
        return x<a.x;
    }
}k;
priority_queue <node> q;
int main()
{
    k.x=10,k.y=100; q.push(k);
    k.x=12,k.y=60; q.push(k);
    k.x=14,k.y=40; q.push(k);
    k.x=6,k.y=80; q.push(k);
    k.x=8,k.y=20; q.push(k);
    while(!q.empty())
    {
        node m=q.top(); q.pop();
        printf("(%d,%d) ",m.x,m.y);
    }
}*/



/*
*测试优先队列基本用法 
*/

/*
//#include<iostream>
 #include<cstdio>
//#include<cstring>
//#include<string>
//#include<algorithm>
//#include<cmath>
//#include<cstdlib>
	#include<queue>
//#include<stack>
//#include<map>
//#include<vector>
//#include<functional>
using namespace std;

priority_queue<int> que1;//声明一个int类型的优先队列 
priority_queue<int,vector<int>,less<int> >que2;//从大到小//注意>>不能相连，因为“>>”是右移运算符
priority_queue<int,vector<int>,greater<int> >que3;//从小到大

int main()
{
	int a[5]={30,41,42,15,54};
	for(int i=0;i<5;i++)
		que1.push(a[i]),que2.push(a[i]),que3.push(a[i]);
	
	for(int i=0;i<5;i++)
	{
		int k=que1.top(); que1.pop();
		printf("%d ",k);
	}
	printf("默认优先队列\n");
	for(int i=0;i<5;i++)
	{
		int k=que2.top(); que2.pop();
		printf("%d ",k);
	}
printf("Less优先队列\n");
	for(int i=0;i<5;i++)
	{
		int k=que3.top(); que3.pop();
		printf("%d ",k);
	}	printf("greater优先队列\n");
	printf("\n");
	return 0;
}*/