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