比赛 |
20150421 |
评测结果 |
WWWAWWWWAW |
题目名称 |
飞越原野 |
最终得分 |
20 |
用户昵称 |
Dijkstra |
运行时间 |
0.004 s |
代码语言 |
C++ |
内存使用 |
0.36 MiB |
提交时间 |
2015-04-21 10:41:38 |
显示代码纯文本
#include<fstream>
#include<cstring>
#include<cmath>
#include<queue>
#define INF 0x7fffffff
#define MAXN 101
#define UP 0
#define DN 1
#define LF 2
#define RT 3
using namespace std;
ifstream fin("escapea.in");
ofstream fout("escapea.out");
struct point
{
int x,y;
int t;
int D;
};
int M,N,D;
bool map[MAXN][MAXN];
int F[MAXN][MAXN];
point make_point(int x,int y,int t,int D)
{
point ans;
ans.x=x;ans.y=y;ans.t=t;ans.D=D;
return ans;
}
int BFS()
{
int j;
queue<point>q;
q.push(make_point(1,1,0,D));
F[1][1]=0;
while(!q.empty())
{
point c=q.front();
q.pop();
if(c.x==M&&c.y==N) return c.t;
if(c.x>1) //UP
{
if(map[c.x-1][c.y])
{
for(j=c.x-1;j>0;j--) if(!map[j][c.y]) break;
if(j!=0&&c.x-j<=c.D&&c.t+1<F[j][c.y]){q.push(make_point(j,c.y,c.t+1,c.D-(c.x-j)));F[j][c.y]=c.t+1;}
}
else if(c.t+1<F[c.x-1][c.y]) {q.push(make_point(c.x-1,c.y,c.t+1,c.D));F[c.x-1][c.y]=c.t+1;}
}
if(c.x<M) //DN
{
if(map[c.x+1][c.y])
{
for(j=c.x+1;j<=M;j++) if(!map[j][c.y]) break;
if(j!=M+1&&j-c.x<=c.D&&c.t+1<F[j][c.y]){q.push(make_point(j,c.y,c.t+1,c.D-(j-c.x)));F[j][c.y]=c.t+1;}
}
else if(c.t+1<F[c.x+1][c.y]) {q.push(make_point(c.x+1,c.y,c.t+1,c.D));F[c.x+1][c.y]=c.t+1;}
}
if(c.y>1) //LF
{
if(map[c.x][c.y-1])
{
for(j=c.y-1;j>0;j--) if(!map[c.x][j]) break;
if(j!=0&&c.y-j<=c.D&&c.t+1<F[c.x][j]){q.push(make_point(c.x,j,c.t+1,c.D-(c.y-j)));F[c.x][j]=c.t+1;}
}
else if(c.t+1<F[c.x][c.y-1]) {q.push(make_point(c.x,c.y-1,c.t+1,c.D));F[c.x][c.y-1]=c.t+1;}
}
if(c.y<N) //RT
{
if(map[c.x][c.y+1])
{
for(j=c.y+1;j<=N;j++) if(!map[c.x][j]) break;
if(j!=N+1&&j-c.y<=c.D&&c.t+1<F[c.x][j]){q.push(make_point(c.x,j,c.t+1,c.D-(j-c.y)));F[c.x][j]=c.t+1;}
}
else if(c.t+1<F[c.x][c.y+1]) {q.push(make_point(c.x,c.y+1,c.t+1,c.D));F[c.x][c.y+1]=c.t+1;}
}
}
return -1;
}
int main()
{
memset(map,0,sizeof(map));
fin>>M>>N>>D;
char ch;
for(int i=1;i<=M;i++)
{
for(int j=1;j<=N;j++)
{
fin>>ch;
map[i][j]=(ch=='L');
F[i][j]=INF;
}
}
int ans=BFS();
if(ans==-1) fout<<"impossible"<<endl;
else fout<<ans<<endl;
return 0;
}