zoj 1649 BFS

// zoj 1649
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
#define MAXN 200
#define INF 1000000
struct point
{
    int x,y;
    int step,time;
};
queue<point> Q;
int N,M,ax,ay;
char map[MAXN][MAXN];
int time[MAXN][MAXN];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int bfs(point s)
{
    int i;
    Q.push(s);
    point jk;
    while(!Q.empty())
    {
        jk=Q.front();
        Q.pop();
        for(i=0; i<4;i++)
        {
            int x=jk.x+dir[i][0];
            int y=jk.y+dir[i][1];
            if(x>=0&&x<=N-1&&y>=0&&y<=M-1&&map[x][y]!='#')
            {
                point t;
                t.x=x;
                t.y=y;
                t.step=jk.step+1;
                t.time=jk.time+1;
                if(map[x][y]=='x')
                    t.time++;
                if(t.time<time[x][y])
                {
                    time[x][y]=t.time;
                    Q.push(t);
                }
            }
        }
    }
    return time[ax][ay];
}
int main()
{
    int i,j;
    //freopen("input.txt","r",stdin);
    while(scanf("%d%d",&N,&M)!=EOF)
    {
        memset(map,0,sizeof(map));
        for(i=0; i<N; i++)
            scanf("%s",map[i]);
        int sx,sy;
        point start;
        for(i=0; i<N; i++)
            for(j=0; j<M; j++)
            {
                time[i][j]=INF;
                if(map[i][j]=='a')
                {
                    ax=i;
                    ay=j;
                }
                else if(map[i][j]=='r')
                {
                    sx=i;
                    sy=j;
                }
            }
        start.x=sx;
        start.y=sy;
        start.step=0;
        start.time=0;
        int min=bfs(start);
        if(min<INF)
            printf("%d\n",min);
        else printf("Poor ANGEL has to stay in the prison all his life.\n");
    }
    return 0;
}