HDU 1242 广搜模板

本文主要是介绍HDU 1242 广搜模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

广搜模板

#include "stdio.h"
#include "string.h"
#include "math.h"
#include "queue"
using namespace std;struct node
{int x,y,step;friend bool operator<(node n1,node n2){return n2.step<n1.step;}
};int dir[4][2]={1,0,-1,0,0,1,0,-1};
int n,m,x_s,y_s;
int map[210][210];int judge(int x,int y)
{if (x<0 || x>=n || y<0 || y>=m) return 0;if (map[x][y]==-1) return 0;return 1;
}
int bfs()
{priority_queue<node>q;node cur,next;int i;cur.x=x_s;cur.y=y_s;cur.step=0;q.push(cur);while (!q.empty()){cur=q.top();q.pop();for (i=0;i<4;i++){next.x=cur.x+dir[i][0];next.y=cur.y+dir[i][1];if (judge(next.x,next.y)==0) continue;next.step=cur.step+1;if (map[next.x][next.y]==1) next.step++;if (map[next.x][next.y]==2) return next.step;map[next.x][next.y]=-1;q.push(next);}}return -1;
}int main()
{int i,ans,j;char str[1010];while (scanf("%d%d",&n,&m)!=EOF){getchar();memset(map,0,sizeof(map));for (i=0;i<n;i++){gets(str);for (j=0;str[j];j++){if (str[j]=='a') { x_s=i; y_s=j;}else if (str[j]=='r') map[i][j]=2;else if (str[j]=='#') map[i][j]=-1;else if (str[j]=='x') map[i][j]=1;}}ans=bfs();if (ans==-1) printf("Poor ANGEL has to stay in the prison all his life.\n");else printf("%d\n",ans);}return 0;
}

这篇关于HDU 1242 广搜模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---