记录编号	159404	评测结果	AAAAAAAAAA
题目名称	飞越原野	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.609 s
提交时间	2015-04-21 12:34:54	内存使用	7.09 MiB

#include <fstream>
#include <deque>
#include <string>
#include <string.h>
using namespace std;
ifstream in("escapea.in");
ofstream out("escapea.out");
struct node
{
	int x,y,p;
};
int m,n,d;
bool h[151][151];//湖泊or沼泽
int visit[121][121][121];//是否访问过
int dir[4][2]={1,0,-1,0,0,1,0,-1};//向量
deque<node> q;
bool SPFA(int x,int y,int p)//判断是否访问过
{
	if(x>=1&&x<=m&&y>=1&&y<=n&&!visit[x][y][p]&&!h[x][y])return 1;
	return 0;
}
int main()
{
	int i,j,size;
	node tmp,tmp2;
	char couple;
	long long ans=0;
	bool flag=0;
	in>>m>>n>>d;
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			in>>couple;
			if(couple=='P')h[i][j]=0;
			else h[i][j]=1;
		}
	}
	memset(visit,0,sizeof(visit));
	tmp.x=tmp.y=1;
	tmp.p=d;//初始状态，在(1,1),能量为d
	visit[tmp.x][tmp.y][tmp.p]=1;
	q.push_back(tmp);
	while(!q.empty())
	{
		size=q.size();
		while(size--)
		{
			tmp=q.front();
			q.pop_front();
			if(tmp.x==m&&tmp.y==n)
			{
				//out<<"fuck"<<endl;
				flag=1;
				break;
			}
			for(i=0;i<4;i++)//不飞行
		    {
				if(SPFA(tmp.x+dir[i][0],tmp.y+dir[i][1],tmp.p))
				{
			       tmp2.x=tmp.x+dir[i][0];
			       tmp2.y=tmp.y+dir[i][1];
			       tmp2.p=tmp.p;
				   visit[tmp2.x][tmp2.y][tmp2.p]=1;
				   q.push_back(tmp2);
				}
		    }
		    for(i=0;i<4;i++)//横向，竖向，斜向
		    {
			    for(j=0;j<=tmp.p;j++)
			    {
				tmp2.x=tmp.x+dir[i][0]*j;
				tmp2.y=tmp.y+dir[i][1]*j;
				tmp2.p=tmp.p-j;//消耗能量
				if(SPFA(tmp2.x,tmp2.y,tmp2.p))
				{
					visit[tmp2.x][tmp2.y][tmp2.p]=1;
					q.push_back(tmp2);
				}
				}
			}
		}
		if(flag==1)break;
		else ans++;
	}
	if(flag)out<<ans<<endl;
	else out<<"impossible"<<endl;
	return 0;
}