裸的优先队列bfs 学会了优先队列
很快写好 但是debug了半个小时 就是应为while里面加了，（a+b) 导致无限超时！！！
优先队列
struct node { int x,y,d; node(int x=0,int y=0,int d=0):x(x),y(y),d(d){} friend bool operator < (node n1,node n2) { return n2.d<n1.d; } }; priority_queue<node> q;
#include<bits/stdc++.h> using namespace std; int n,m,sx,sy; char m1[500][500]; bool f[500][500]; bool flag=false; struct node { int x,y,d; node(int x=0,int y=0,int d=0):x(x),y(y),d(d){} friend bool operator < (node n1,node n2) { return n2.d<n1.d; } }; void bfs() { int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; memset(f,false,sizeof(f)); node u(sx,sy,0); priority_queue<node> q; //queue<node>q; q.push(u); while(!q.empty()) { node u=q.top();q.pop(); // printf("%d %d %d ",u.x,u.y,u.d); if(m1[u.x][u.y]=='r') {printf("%d ",u.d);return;} for(int i=0;i<4;i++) { node v(u.x+dx[i],u.y+dy[i],u.d+1); if(v.x>=1&&v.x<=n&&v.y>=1&&v.y<=m&&m1[v.x][v.y]!='#'&&!f[v.x][v.y]) { if(m1[v.x][v.y]=='x') { f[v.x][v.y]=true;v.d++; q.push(v); } else if((m1[v.x][v.y]=='r'||m1[v.x][v.y]=='.')) { f[v.x][v.y]=true; q.push(v); } } } } printf("Poor ANGEL has to stay in the prison all his life. "); } int main() { while(scanf("%d%d",&n,&m)==2) { for(int i=1;i<=n;i++) { scanf("%s",m1[i]+1); for(int j=1;j<=m;j++) {if(m1[i][j]=='a'){sx=i;sy=j; } } } bfs(); } return 0; }