題目：http://acm.hdu.edu.cn/showproblem.php?pid=1242

這題目就是個大坑，先說下思路就是在遇到‘x’時要多停留1步，另外就是要用到優先隊列，要從小到大排列，另外就是普通的bfs了

但是要注意題里的each of Angel's friend數據里其實就一個‘r’的位置，但我當多個‘r’做應該也沒錯就是wa想不通啊 這是我按一個‘r’做的。 #include<stdio.h> #include<string.h> #include <iostream> #include <queue> using namespace std; struct in {char b;int x;int y;int t;friend bool operator < (in a, in b){return a.t > b.t; } };int x, y, m, n;; char a[205][205],map[205][205]; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; priority_queue<in>p; int bfs(int xx,int yy) { if(xx==x&&yy==y)return 0;in tt,next;tt.x=xx;tt.y=yy;tt.b=a[xx][yy];tt.t=0;p.push(tt);while(!p.empty()){tt=p.top();p.pop();a[tt.x][tt.y]='#';if(tt.x==x&&tt.y==y){return tt.t;}for(int i= 0; i< 4; i++){next.x=tt.x+dir[i][0];next.y=tt.y+dir[i][1];next.t=tt.t+1;if(a[next.x][next.y]=='x')next.t++;if(a[next.x][next.y]!='#'&& next.x< n&& next.x>=0&&next.y<m&&next.y>=0)p.push(next);}}return -1; } int main() {while(~scanf("%d%d", &n, &m)){int x1, y1;memset(map,0,sizeof(map));memset(a,0,sizeof(a));for(int i= 0; i< n; i++){getchar();for(int j= 0; j< m; j++){scanf("%c",&a[i][j]);map[i][j]=a[i][j];if(a[i][j]=='r'){x1=i;y1=j;}if(a[i][j]=='a'){x= i;y= j;}}} int ans=1000000;int u;u=bfs(x1,y1);ans=u;if(ans==-1)printf("Poor ANGEL has to stay in the prison all his life.\n");elseprintf("%d\n",ans);while(!p.empty()){p.pop();}}return 0; } View Code

?

轉載于:https://www.cnblogs.com/Arthas0v0/p/3456244.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的bfs+优先队列（hdu1242）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。