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