记录编号	36436	评测结果	AAAAAAAAAA
题目名称	飞越原野	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.736 s
提交时间	2012-03-13 19:17:42	内存使用	16.48 MiB

#include <cstdio>
using namespace std;

const short RUL[4][2]={{0,-1},{0,1},{-1,0},{1,0}};

struct quetype
{
	int x,y,d,deep/*,right*/;
}que[1000002];

bool used[100][100][100]={0};

char map[102][102];
/*
bool dup(int top)
{
	int i;
	for (i=0;i<top;i++)
		if (que[i].right==que[top].right)
			return(true);
	return(false);
}
*/
int main(void)
{
	freopen("escapea.in","r",stdin);
	freopen("escapea.out","w",stdout);
	int i,j,m,n,d,tx,ty,head=0,tail=0;
	bool done=false;
	scanf("%d%d%d\n",&m,&n,&d);
	for (i=1;i<=m;i++)
	{
		for (j=1;j<=n;j++)
			scanf("%c",&map[i][j]);
		scanf("\n");
	}
	que[0].x=1;
	que[0].y=1;
	que[0].d=d;
	que[0].deep=0;
//	que[0].right=1*10000+1*100+d;
	while (head>=tail)
	{
		for (i=0;!done&&i<=3;i++)
		{
			for (j=2;!done&&j<=que[tail].d;j++)
			{
				tx=j*RUL[i][0]+que[tail].x;
				ty=j*RUL[i][1]+que[tail].y;
				if (tx>=1&&tx<=m&&ty>=1&&ty<=n&&map[tx][ty]=='P')
				{
					head++;
					que[head].x=tx;
					que[head].y=ty;
					que[head].d=que[tail].d-j;
					que[head].deep=que[tail].deep+1;
//					que[head].right=tx*10000+ty*100+que[head].d;
					if (tx==m&&ty==n)
						done=true;
					if (done)
						break;
					if (used[tx][ty][que[head].d])
						head--;
					else
						used[tx][ty][que[head].d]=true;
//					if (dup(head))
//						head--;
				}
			}
		}
		for (i=0;!done&&i<=3;i++)
		{
			tx=RUL[i][0]+que[tail].x;
			ty=RUL[i][1]+que[tail].y;
			if (tx>=1&&tx<=m&&ty>=1&&ty<=n&&map[tx][ty]=='P')
			{
				head++;
				que[head].x=tx;
				que[head].y=ty;
				que[head].d=que[tail].d;
				que[head].deep=que[tail].deep+1;
//				que[head].right=tx*10000+ty*100+que[head].d;
				if (tx==m&&ty==n)
					done=true;
				if (done)
					break;
				if (used[tx][ty][que[head].d])
					head--;
				else
					used[tx][ty][que[head].d]=true;
//				if (dup(head))
//					head--;
			}
		}
		if (done)
			break;
		tail++;
	}
	if (done)
		printf("%d\n",que[head].deep);
	else
		printf("impossible\n");
	return(0);
}