记录编号	36217	评测结果	AAAAAAAAAA
题目名称	飞越原野	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.505 s
提交时间	2012-03-10 14:50:37	内存使用	16.55 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct hehe
{
	int x0,y0,t,neng;
}q[1000001];
int w[101][101],f[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int m,n,d,tou,wei,answer=10000000;
bool visited[101][101][101]={0};
void bfs(int x);
int main()
{
	freopen ("escapea.in","r",stdin);
	freopen ("escapea.out","w",stdout);
	cin>>m>>n>>d;
	for (int i=1;i<=m;i++)
	{
		for (int j=1;j<=n;j++)
		{
			char a;
			cin>>a;
			if (a=='P')
				w[i][j]=1;
			else
				w[i][j]=0;
			for (int k=0;k<=d;k++)
			{
				visited[i][j][k]=0;
			}
		}
	}
	q[0].x0=1;
	q[0].y0=1;
	q[0].t=0;
	q[0].neng=d;
	tou=0;
	wei=0;
	while (tou<=wei)
	{
		bfs(tou);
		tou++;
		if (q[tou].x0==m&&q[tou].y0==n)
		{
			cout<<q[tou].t;
			return 0;
		}
	}
	cout<<"impossible";
	return 0;
}
void bfs(int x)
{
	for (int i=0;i<4;i++)
	{
		int nx,ny;
		nx=q[x].x0+f[i][0];
		ny=q[x].y0+f[i][1];
		if(ny>n||nx>m||nx<=0||ny<=0)
		{
			continue;
		}
		if (!w[nx][ny])
		{
		}
		else if(!visited[nx][ny][q[x].neng])
		{
			wei++;
			q[wei].x0=nx;
			q[wei].y0=ny;
			q[wei].t=q[x].t+1;
			q[wei].neng=q[x].neng;
			visited[nx][ny][q[x].neng]=1;
		}
		for (int j=2;j<=q[x].neng;++j)
		{
			int xx,yy;
			xx=q[x].x0+j*f[i][0];
			yy=q[x].y0+j*f[i][1];
			if (yy>n||xx>m||xx<=0||yy<=0)
			{
				break;
			}
			if (!w[xx][yy])
			{
				continue;
			}
			else if (!visited[xx][yy][q[x].neng-j])
			{
				wei++;
				q[wei].x0=xx;
				q[wei].y0=yy;
				q[wei].t=q[x].t+1;
				q[wei].neng=q[x].neng-j;
				visited[xx][yy][q[x].neng-j]=1;
			}
		}
	}
}