记录编号	159440	评测结果	AAAAAAAAAA
题目名称	飞越原野	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.252 s
提交时间	2015-04-21 14:55:48	内存使用	10.00 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;
#define USEFREAD
#ifdef USEFREAD
#define InputLen 5000000
char *ptr=(char *)malloc(InputLen);
#define getc() (*(ptr++))
#else
#define getc() (getchar())
#endif
#define SetFile(x) (freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout))
template<class T>inline void getd(T &x){
    char ch = getc();bool neg = false;
    while(!isdigit(ch) && ch != '-')ch = getc();
    if(ch == '-')ch = getc(), neg = true;
    x = ch - '0';
    while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
    if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 101, inf = 0x3f3f3f3f;
int M, N, D, dis[maxn][maxn][maxn];//dis[消耗魔法][x][y]
bool G[maxn][maxn];

inline void init(){
	getd(M), getd(N), getd(D);
	int i, j, ch;
	for(i = 0;i < M;++i){
		while(!isalpha(ch = getc()));
		for(j = 0;j < N;++j, ch = getc())G[i][j] = (ch == 'L');
	}
	memset(dis, 0x3f, sizeof(dis));
	***dis = 0;
}

struct Tp{int d, x, y;};
#include <queue>
queue<Tp> Q;bool vis[maxn][maxn][maxn];
inline void UPD(int d, int x, int y, int dist){
	if(x < 0 || x >= M || y < 0 || y >= N || G[x][y] || vis[d][x][y])return;
	dis[d][x][y] = dist;
	vis[d][x][y] = true, Q.push((Tp){d, x, y});
}
inline void getdis(){
	vis[0][0][0] = true;
	Q.push((Tp){0,0,0});
	Tp tmp;
	int d, x, y, cur, i, lastd;
	bool flag;
	while(!Q.empty()){
		tmp = Q.front();Q.pop();
		d = tmp.d, x = tmp.x, y = tmp.y;
		cur = dis[d][x][y] + 1;
		UPD(d, x+1, y, cur);
		UPD(d, x-1, y, cur);
		UPD(d, x, y+1, cur);
		UPD(d, x, y-1, cur);
		lastd = D - d;
		flag = true;
		for(i = 2;i <= lastd && flag;++i){
			flag = false;
			if(x+i < M)UPD(d+i, x+i, y, cur), flag = true;
			if(x-i >= 0)UPD(d+i, x-i, y, cur), flag = true;
			if(y+i < N)UPD(d+i, x, y+i, cur), flag = true;
			if(y-i >= 0)UPD(d+i, x, y-i, cur), flag = true;
		}
	}
}

int main(){
	#ifdef DEBUG
	freopen("test.txt", "r", stdin);
	#else       
	SetFile(escapea);
	#endif
	#ifdef USEFREAD
	fread(ptr,1,InputLen,stdin);
	#endif
	
	init();
	
	getdis();
	
	int Ans = inf, d;
	for(d = 0;d <= D;++d)Ans = min(Ans, dis[d][M-1][N-1]);
	if(Ans == inf)puts("impossible");
	else printf("%d\n", Ans);
	
#ifdef DEBUG
    printf("\n%.3lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
    return 0;
}