记录编号	159534	评测结果	AAAAAAAAAA
题目名称	飞越原野	最终得分	100
用户昵称	devil	是否通过	通过
代码语言	C++	运行时间	0.325 s
提交时间	2015-04-21 18:27:27	内存使用	1.63 MiB

#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];
bool vis[maxn][maxn][maxn];
int dx[]={0,0,1,0,-1};
int dy[]={0,1,0,-1,0};

struct node
{
    int x,y;
    int rd,times;
    node() {x=y=rd=times=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=0;
    vis[s.x][s.y][s.rd]=true;
    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++)
        {
            int nx=t.x+dx[i];
            int ny=t.y+dy[i];
            if(inG(nx,ny)&&!vis[nx][ny][t.rd]&&G[nx][ny]==1)
            {
                vis[nx][ny][t.rd]=true;
                node nt;nt=t;
                nt.x=nx;nt.y=ny;
                nt.times++;
                q.push(nt);
            }
            for(int j=2;j<=t.rd;j++)
            {
                nx=t.x+j*dx[i];
                ny=t.y+j*dy[i];
                if(inG(nx,ny)&&!vis[nx][ny][t.rd-j]&&G[nx][ny]==1)
                {
                    vis[nx][ny][t.rd-j]=true;
                    node nt;nt=t;
                    nt.times++;
                    nt.x=nx;nt.y=ny;
                    nt.rd-=j;
                    q.push(nt);
                }
            }
        }
    }
    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);
    memset(vis,false,sizeof(vis));
    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;
}