记录编号	36174	评测结果	AAAAAAAAAA
题目名称	飞越原野	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.621 s
提交时间	2012-03-09 22:25:05	内存使用	5.52 MiB

#include <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;
const int MAXN=111;
const int INF=1000000000;
int Map[MAXN][MAXN];
int F[MAXN][MAXN][MAXN];
const int step[5][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}};
int Ans=0;
int N,M,D;

void init()
{
	scanf("%d %d %d\n",&M,&N,&D);
	char c;
	for(int i=1;i<=M;i++)
	{
		for(int j=1;j<=N;j++)
		{
			scanf("%c",&c);
			while(c==10 || c==13) scanf("%c",&c);
			if(c=='P') Map[i][j]=1;
			if(c=='L') Map[i][j]=0;
		}
	}
}

class QUEUE
{
public:
	int x,y,f;
};
queue<QUEUE> Q;

void MS()
{
	for(int i=1;i<=M;i++)
		for(int j=1;j<=N;j++)
			for(int k=0;k<=D;k++)
				F[i][j][k]=INF;
	F[1][1][D]=0;
	QUEUE tmp,nxt;
	tmp.x=1,tmp.y=1,tmp.f=D;
	Q.push(tmp);
	int tx,ty,tf,ts;
	int nx,ny,nf,ns; 
	while(!Q.empty())
	{
		tmp=Q.front();
		Q.pop();
		tx=tmp.x;
		ty=tmp.y;
		tf=tmp.f;
		ts=F[tx][ty][tf];
		/*移動*/
		nf=tf;
		for(int i=1;i<=4;i++)
		{
			nx=tx+step[i][0];
			ny=ty+step[i][1];
			if(nx<1 || nx>M || ny<1 || ny>N) continue;
			if(Map[nx][ny]==0) continue;
			ns=ts+1;
			if(F[nx][ny][nf]<=ns) continue;
			F[nx][ny][nf]=ns;
			nxt.x=nx;
			nxt.y=ny;
			nxt.f=nf;
			Q.push(nxt);
		}
		
		for(int i=1;i<=4;i++)
		{ 
			nx=tx;
			ny=ty;
			nf=tf;
			
			ns=ts+1;
			nx+=step[i][0];
			ny+=step[i][1];
			nf--;
			while(nf>=0 && nx<=M && nx>=1 && ny>=1 && ny<=N)
			{
				if(Map[nx][ny]==1)
				{
					if(F[nx][ny][nf]>ns)
					{
						F[nx][ny][nf]=ns;
						nxt.x=nx;
						nxt.y=ny;
						nxt.f=nf;
						Q.push(nxt);
					}
				}
				nx+=step[i][0];
				ny+=step[i][1];
				nf--;
			}
		}
	}
	int Min=INF;
	for(int i=0;i<=D;i++)
		if(F[M][N][i]<Min)
			Min=F[M][N][i];
	if(Min==INF) printf("impossible\n");
	else printf("%d\n",Min);
}

int main() 
{
	freopen("escapea.in","r",stdin);
	freopen("escapea.out","w",stdout);
	init();
	MS();
	return 0;
}