记录编号	159473	评测结果	AAAAAAAAAA
题目名称	飞越原野	最终得分	100
用户昵称	Dijkstra	是否通过	通过
代码语言	C++	运行时间	0.216 s
提交时间	2015-04-21 16:56:26	内存使用	2.29 MiB

#include<fstream>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
#define MAXN 101
using namespace std;
ifstream fin("escapea.in");
ofstream fout("escapea.out");
struct point
{
	int x,y,t,d;
};
bool v[MAXN][MAXN][MAXN];
bool v2[MAXN][MAXN][MAXN];
bool m[MAXN][MAXN];
int N,M,D;
point mp(int _x,int _y,int _t,int _d)
{
	point a;
	a.x=_x;a.y=_y;a.t=_t;a.d=_d;
	return a;
}
void INPUT()
{
	char ch;
	memset(m,0,sizeof(m));
	fin>>M>>N>>D;
	for(int i=1;i<=M;i++)for(int j=1;j<=N;j++){fin>>ch;m[i][j]=(ch=='L');}
}
int bfs()
{
	point tmp;
	queue<point>q;
	memset(v,0,sizeof(v));
	memset(v2,0,sizeof(v2));
	tmp=mp(1,1,0,D);
	q.push(tmp);
	v[1][1][D]=1;
	while(!q.empty())
	{
		point c=q.front();
		q.pop();
		//cout<<c.x<<" "<<c.y<<" "<<c.d<<endl;
		if(v2[c.x][c.y][c.d]&&c.x!=1) continue;
		if(c.x==M&&c.y==N) return c.t;
		/*UP*/
		for(int i=c.x-1;i>0;i--)
		{
			if(c.d-(c.x-i)<0) break;
			if(!m[i][c.y]&&!v[i][c.y][c.d-(c.x-i)]){tmp=mp(i,c.y,c.t+1,c.d-(c.x-i));q.push(tmp);v[i][c.y][c.d-(c.x-i)]=1;}
		}
		if(c.x>1&&!m[c.x-1][c.y]&&!v[c.x-1][c.y][c.d]){tmp=mp(c.x-1,c.y,c.t+1,c.d);q.push(tmp);v[c.x-1][c.y][c.d]=1;}
		/*DN*/
		for(int i=c.x+1;i<=M;i++)
		{
			if(c.d-(i-c.x)<0) break;
			if(!m[i][c.y]&&!v[i][c.y][c.d-(c.x-i)]){tmp=mp(i,c.y,c.t+1,c.d-(i-c.x));q.push(tmp);v[i][c.y][c.d-(i-c.x)]=1;}
		}
		if(c.x<M&&!m[c.x+1][c.y]&&!v[c.x+1][c.y][c.d]){tmp=mp(c.x+1,c.y,c.t+1,c.d);q.push(tmp);v[c.x+1][c.y][c.d]=1;}
		/*LF*/
		for(int i=c.y-1;i>0;i--)
		{
			if(c.d-(c.y-i)<0) break;
			if(!m[c.x][i]&&!v[c.x][i][c.d-(c.y-i)]){tmp=mp(c.x,i,c.t+1,c.d-(c.y-i));q.push(tmp);v[c.x][i][c.d-(c.y-i)]=1;}
		}
		if(c.y>1&&!m[c.x][c.y-1]&&!v[c.x][c.y-1][c.d]){tmp=mp(c.x,c.y-1,c.t+1,c.d);q.push(tmp);v[c.x][c.y-1][c.d]=1;}
		/*RT*/
		for(int i=c.y+1;i<=N;i++)
		{
			if(c.d-(i-c.y)<0) break;
			if(!m[c.x][i]&&!v[c.x][i][c.d-(i-c.y)]){tmp=mp(c.x,i,c.t+1,c.d-(i-c.y));q.push(tmp);v[c.x][i][c.d-(i-c.y)]=1;}
		}
		if(c.y<N&&!m[c.x][c.y+1]&&!v[c.x][c.y+1][c.d]){tmp=mp(c.x,c.y+1,c.t+1,c.d);q.push(tmp);v[c.x][c.y+1][c.d]=1;}
		v2[c.x][c.y][c.d]=1;
	}
	return -1;
}
void OUTPUT(){int ans=bfs();if(ans==-1)fout<<"impossible"<<endl;else fout<<ans<<endl;}
int main()
{
	INPUT();
	OUTPUT();
    return 0;
}