HDU 1242 Rescue BFS

题意：有几个旁友找小爱，走有守卫的格子相当于走两格，求找到小爱最少格子数。

题解：一开始我没有考虑异步的问题，这就导致有可能必须搜完全图才能得到答案。

队列改成优先队列，每次都让步数少的优先出队就阔以了。

#include <iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
char mp[205][205];
int vis[205][205];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int n,m,px,py;
struct node
{
	int x,y,step;
	friend bool operator <(node a,node b){
		return a.step>b.step;
     	}
};
bool check(int x,int y){
	if(x<0||x>=n||y<0||y>=m)return true;
	if(vis[x][y])return true;
	if(mp[x][y]=='#')return true;
	return false;
}
int bfs(int x,int y){
	priority_queue<node> que;
	node a,next;
	int i,xx,yy;
	vis[x][y]=1;
	a.x=x;
	a.y=y;
	a.step=0;
	que.push(a);
	while(!que.empty()){
		a=que.top();
		que.pop();
		if(mp[a.x][a.y]=='r')return a.step;
		for(i=0;i<4;i++){
			xx=a.x+dir[i][0];
			yy=a.y+dir[i][1];
			if(check(xx,yy))continue;
			next.x=xx;
			next.y=yy;
			vis[xx][yy]=1;
			next.step=a.step+1;
			if(mp[xx][yy]=='x')next.step++;
			que.push(next);
		}
	}
	return -1;
}
int main()
{
	int i,j;
	while(~scanf("%d%d",&n,&m)){
		memset(vis,0,sizeof(vis));
		getchar();
		for(i=0;i<n;i++){
			for(j=0;j<m;j++){
				mp[i][j]=getchar();
				if(mp[i][j]=='a')px=i,py=j;
			}
			getchar();
		}
		int ans=bfs(px,py);
		if(ans==-1)printf("Poor ANGEL has to stay in the prison all his life.n");
		else printf("%dn",ans);
	}
  //  cout << "Hello world!" << endl;
    return 0;
}

最后

以上就是细腻大白为你收集整理的HDU 1242 Rescue BFS的全部内容，希望文章能够帮你解决HDU 1242 Rescue BFS所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。