比赛 |
20150421 |
评测结果 |
AAAAAAAAAA |
题目名称 |
飞越原野 |
最终得分 |
100 |
用户昵称 |
Asm.Def |
运行时间 |
0.489 s |
代码语言 |
C++ |
内存使用 |
10.00 MiB |
提交时间 |
2015-04-21 08:56:40 |
显示代码纯文本
#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;
}