比赛 20120309 评测结果 AAAAAAAAAA
题目名称 飞越原野 最终得分 100
用户昵称 Czb。 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-03-09 21:43:01
显示代码纯文本
#include<stdio.h>
#include<string.h>

struct kaaala
{
	int x,y,z,time;
	kaaala()
	{
		x=y=z=time=0;
	}
}q[1200001];

int n,m,k,ans;

bool g[102][102],flag[102][102][102];

char c;

int main()
{
	freopen("escapea.in","r",stdin);
	freopen("escapea.out","w",stdout);
	int i,j,l,r,x,y,z;
	scanf("%d%d%d\n",&n,&m,&k);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			scanf("%c",&c);
			if(c=='P')
			{
				g[i][j]=true;
			}
		}
		scanf("\n");
	}
	memset(flag,1,sizeof(flag));
	ans=0x7FFFFFFF;
	flag[1][1][k]=false;
	l=r=1;
	q[1].x=q[1].y=1;
	q[1].z=k;
	q[1].time=0;
	while(l<=r)
	{
		x=q[l].x;
		y=q[l].y;
		z=q[l].z;
		if(x==n&&y==m)
		{
			if(q[l].time<ans)
				ans=q[l].time;
		}
		if(flag[x-1][y][z]&&g[x-1][y])
		{
			r++;
			q[r]=q[l];
			q[r].x--;
			q[r].time++;
			flag[x-1][y][z]=false;
		}
		if(flag[x+1][y][z]&&g[x+1][y])
		{
			r++;
			q[r]=q[l];
			q[r].x++;
			q[r].time++;
			flag[x+1][y][z]=false;
		}
		if(flag[x][y-1][z]&&g[x][y-1])
		{
			r++;
			q[r]=q[l];
			q[r].y--;
			q[r].time++;
			flag[x][y-1][z]=false;
		}
		if(flag[x][y+1][z]&&g[x][y+1])
		{
			r++;
			q[r]=q[l];
			q[r].y++;
			q[r].time++;
			flag[x][y+1][z]=false;
		}
		for(i=2;i<=z;i++)
		{
			if(x>i)
			{
				if(flag[x-i][y][z-i]&&g[x-i][y])
				{
					r++;
					q[r]=q[l];
					q[r].x-=i;
					q[r].z-=i;
					q[r].time++;
					flag[x-1][y][z-i]=false;
				}
			}
			if(x+i<=n)
			{
				if(flag[x+i][y][z-i]&&g[x+i][y])
				{
					r++;
					q[r]=q[l];
					q[r].x+=i;
					q[r].z-=i;
					q[r].time++;
					flag[x+i][y][z-i]=false;
				}
			}
			if(y>i)
			{
				if(flag[x][y-i][z-i]&&g[x][y-i])
				{
					r++;
					q[r]=q[l];
					q[r].y-=i;
					q[r].z-=i;
					q[r].time++;
					flag[x][y-i][z-i]=false;
				}
			}
			if(i+y<=m)
			{
				if(flag[x][y+i][z-i]&&g[x][y+i])
				{
					r++;
					q[r]=q[l];
					q[r].y+=i;
					q[r].z-=i;
					q[r].time++;
					flag[x][y+i][z-i]=false;
				}
			}
		}
		l++;
	}
	if(ans==0x7FFFFFFF)
	{
		printf("impossible\n");
		return 0;
	}
	printf("%d\n",ans);
	return 0;
}