bfs+优先队列（hdu1242）

题目：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）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。