ZOJ 1649 Rescue BFS水题

要注意的是队列里入队条件有些变化

#include<stdio.h>
#include<queue>
#include<string.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
int n,m,sx,sy,ex,ey;
char map[210][210];
int mini[210][210];
int h[4]={1,-1,0,0};
int g[4]={0,0,1,-1};
struct point{
	int x;
	int y;
	int time;
};
void bfs(){
	struct point cur;
	cur.x=sx;
	cur.y=sy;
	cur.time=0;
	queue<struct point> que;
	que.push(cur);

	while(!que.empty()){
		struct point tem;
		tem=que.front();
		que.pop();

		for(int i=0;i<4;i++){
			int xx=tem.x+h[i];
			int yy=tem.y+g[i];
			if(xx<0 || xx>=n || yy<0 || yy>=m)
				continue;
			if(map[xx][yy]=='#')
				continue;
			if(map[xx][yy]=='a'){
				if(tem.time+1<mini[xx][yy])
					mini[xx][yy]=tem.time+1;
			}
			else if(map[xx][yy]=='.'){
				if(tem.time+1<mini[xx][yy]){
					mini[xx][yy]=tem.time+1;
					struct point pp;
					pp.x=xx;pp.y=yy;pp.time=tem.time+1;
					que.push(pp);
				}
			} 
			else if(map[xx][yy]=='x'){
				if(tem.time+2<mini[xx][yy]){
					mini[xx][yy]=tem.time+2;
					struct point pp;
					pp.x=xx;pp.y=yy;pp.time=tem.time+2;
					que.push(pp);
				}
			} 

		}
	}
}
int main(){
	int i,j;
	while(scanf("%d %d",&n,&m)!=EOF){
		for(i=0;i<n;i++)
			scanf("%s",map[i]);
	
		for(i=0;i<n;i++)
			for(j=0;j<m;j++){
				if(map[i][j]=='r'){
					sx=i;
					sy=j;
				}
				else if(map[i][j]=='a'){
					ex=i;
					ey=j;
				}
				mini[i][j]=1000000;
			}
		mini[sx][sy]=0;
		bfs();
		if(mini[ex][ey]==1000000){
			printf("Poor ANGEL has to stay in the prison all his life.\n");
		}
		else
			printf("%d\n",mini[ex][ey]);
	}
	return 0;
	
}