zoj 1649

#include <iostream>
#include <queue>
using namespace std;
int n,m,s2,e2;
int b[205][205],d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char a[205][205];
struct point{
	int x,y,step;
}p;
queue <point> q;
int bfs(point pp)
{
	int i,j,k;
	point t;
	q.push(pp);
	while(!q.empty())
	{
		p=q.front(),q.pop();
	for(i=0;i<4;i++)
	{
		j=p.x+d[i][0]; k=p.y+d[i][1];
		if(j>=0&&j<n&&k>=0&&k<m&&a[j][k]!='#')
		{
		t.x=j;  t.y=k;	t.step=p.step+1;
			if(a[j][k]=='x') t.step++;
			if(t.step<b[j][k]) q.push(t), b[j][k]=t.step;
		}
	}
	}
	return b[s2][e2];
}
int main(int argc, char *argv[])
{
	int i,j,k;
	while(cin>>n>>m)
	{
	for(i=0;i<n;i++)
	for(j=0;j<m;j++)
	{
	cin>>a[i][j]; b[i][j]=1000000;
	if(a[i][j]=='a') p.x=i,p.y=j;
	if(a[i][j]=='r') s2=i,e2=j;
	}
	p.step=0; b[p.x][p.y]=0;
	k=bfs(p);
	if(k==1000000) 
	cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
	else cout<<k<<endl;
	}
	return 0;
}