比赛 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;
}