比赛 |
20120309 |
评测结果 |
AAAAAAAAAA |
题目名称 |
飞越原野 |
最终得分 |
100 |
用户昵称 |
Makazeu |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2012-03-09 21:05:13 |
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;
const int MAXN=111;
const int INF=1000000000;
int Map[MAXN][MAXN];
int F[MAXN][MAXN][MAXN];
const int step[5][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}};
int Ans=0;
int N,M,D;
void init()
{
scanf("%d %d %d\n",&M,&N,&D);
char c;
for(int i=1;i<=M;i++)
{
for(int j=1;j<=N;j++)
{
scanf("%c",&c);
while(c==10 || c==13) scanf("%c",&c);
if(c=='P') Map[i][j]=1;
if(c=='L') Map[i][j]=0;
}
}
}
class QUEUE
{
public:
int x,y,f;
};
queue<QUEUE> Q;
void MS()
{
for(int i=1;i<=M;i++)
for(int j=1;j<=N;j++)
for(int k=0;k<=D;k++)
F[i][j][k]=INF;
F[1][1][D]=0;
QUEUE tmp,nxt;
tmp.x=1,tmp.y=1,tmp.f=D;
Q.push(tmp);
int tx,ty,tf,ts;
int nx,ny,nf,ns;
while(!Q.empty())
{
tmp=Q.front();
Q.pop();
tx=tmp.x;
ty=tmp.y;
tf=tmp.f;
ts=F[tx][ty][tf];
/*移動*/
nf=tf;
for(int i=1;i<=4;i++)
{
nx=tx+step[i][0];
ny=ty+step[i][1];
if(nx<1 || nx>M || ny<1 || ny>N) continue;
if(Map[nx][ny]==0) continue;
ns=ts+1;
if(F[nx][ny][nf]<=ns) continue;
F[nx][ny][nf]=ns;
nxt.x=nx;
nxt.y=ny;
nxt.f=nf;
Q.push(nxt);
}
for(int i=1;i<=4;i++)
{
nx=tx;
ny=ty;
nf=tf;
ns=ts+1;
nx+=step[i][0];
ny+=step[i][1];
nf--;
while(nf>=0 && nx<=M && nx>=1 && ny>=1 && ny<=N)
{
if(Map[nx][ny]==1)
{
if(F[nx][ny][nf]>ns)
{
F[nx][ny][nf]=ns;
nxt.x=nx;
nxt.y=ny;
nxt.f=nf;
Q.push(nxt);
}
}
nx+=step[i][0];
ny+=step[i][1];
nf--;
}
}
}
int Min=INF;
for(int i=0;i<=D;i++)
if(F[M][N][i]<Min)
Min=F[M][N][i];
if(Min==INF) printf("impossible\n");
else printf("%d\n",Min);
}
int main()
{
freopen("escapea.in","r",stdin);
freopen("escapea.out","w",stdout);
init();
MS();
return 0;
}