比赛 |
20150421 |
评测结果 |
WWWWWEWEEW |
题目名称 |
飞越原野 |
最终得分 |
0 |
用户昵称 |
devil |
运行时间 |
1.136 s |
代码语言 |
C++ |
内存使用 |
0.36 MiB |
提交时间 |
2015-04-21 11:25:12 |
显示代码纯文本
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf=0x7fffffff;
const int mod=10007;
const int maxn=110;
int m,n,d;
int G[maxn][maxn];
int dx[]={0,0,1,0,-1};
int dy[]={0,1,0,-1,0};
struct node
{
int x,y;
int rd,times;
int from;
node() {x=y=rd=times=from=0;}
};
bool ing(int x,int y)
{
if(x>0&&x<=n&&y>0&&y<=m) return true;
else return false;
}
void BFS()
{
queue<node> q;
node s;
s.x=s.y=1;
s.rd=d;s.times=1;
s.from=0;
q.push(s);
while(!q.empty())
{
node t;t=q.front();
q.pop();
if(t.x==n&&t.y==m) {printf("%d\n",t.times);return;}
for(int i=1;i<=4;i++)
{
if(i==t.from) continue;
if(ing(t.x+dx[i],t.y+dy[i]))
{
int nx=t.x+dx[i];
int ny=t.y+dy[i];
int l=0;int all=1;
while(ing(nx,ny))
{
if(G[nx][ny]==0) l++;
else if(G[nx][ny]==1)
{
if(l==0)
{
node nt;
nt=t;
nt.x=nx;
nt.y=ny;
nt.times+=all;
nt.from=i;
nt.rd-=l;
q.push(nt);
}
if(t.rd>=l)
{
node nt;
nt=t;
nt.x=nx;
nt.y=ny;
nt.times++;
nt.from=i;
nt.rd-=l;
q.push(nt);
}
}
nx+=dx[i];ny+=dy[i];all++;
}
}
}
}
printf("impossible\n");
}
int main()
{
///freopen("sample_data.in","r",stdin);
///freopen("data.in","r",stdin);
freopen("escapea.in","r",stdin);
freopen("escapea.out","w",stdout);
scanf("%d%d%d\n",&n,&m,&d);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
char c;scanf("%c",&c);
if(c=='P') G[i][j]=1;
}
scanf("\n");
}
BFS();
return 0;
}