记录编号	159481	评测结果	AAAAAAAAAA
题目名称	飞越原野	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.476 s
提交时间	2015-04-21 17:20:22	内存使用	30.01 MiB

#include<cstdio>
#include<deque>
#include<iostream>
using namespace std;
int n,m,mp[101][101]={0},dp[110][110][101][5],d;
int maxn=0xffffff;
int ans=maxn;
bool z[110][110][110][5]={0};
class miku 
{
public:
	int x,y;
	int p,to;
	int& val(void)
	{
		return dp[x][y][p][to];
	}
	bool& iq (void)
	{
	return z[x][y][p][to];
	}
};
deque<miku> Q;
int dx[]={0,0,0,1,-1},dy[]={0,1,-1,0,0};
void check(miku a,int b)
{
	if(b<a.val())
	{
		a.val()=b;
		if(!a.iq())
		{
			a.iq()=true;
			Q.push_back(a);
		}
	}
}
int main()
{
	freopen("escapea.in","r",stdin);
	freopen("escapea.out","w",stdout);
	scanf("%d%d%d",&n,&m,&d);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			char a;
			cin>>a;
			if(a=='P')
			mp[i][j]=1;
			else
				mp[i][j]=0;
			//cout<<mp[i][j];
        }
		//cout<<endl;
	}
	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
			for(int k=0;k<=d;k++)
				for(int d=0;d<=4;d++)
					dp[i][j][k][d]=maxn;
	miku x;
	while(!Q.empty()) Q.pop_front();
	x.x=1;x.y=1;x.p=d;x.to=0;
	x.val()=0;
	x.iq()=true;
	Q.push_back(x);
	miku s,t;
	//cout<<Q.size()<<endl;
	while(!Q.empty())
	{
		s=Q.front();Q.pop_front();s.iq()=0;int w=s.val();
		if(s.to!=0)
		{
			if(mp[s.x][s.y]==1)
			{
				t=s;
				t.to=0;
				check(t,w);
			}
		t=s;
		t.x+=dx[s.to];t.y+=dy[s.to];t.p--;
		if(1<=t.x&&t.x<=n&&1<=t.y&&t.y<=m&&t.p>=0) check(t,w);
		}
		else
		{
			for(int k=1;k<=4;k++)
			{
				t=s;
				t.x+=dx[k],t.y+=dy[k];
				if(1<=t.x&&t.x<=n&&1<=t.y&&t.y<=m&&mp[t.x][t.y]==1) check(t,w+1);
			}
			for(int k=1;k<=4;k++)
			{
				t=s;t.to=k;
				check(t,w+1);
			}
		}
	}
	for(int i=0;i<=d;i++)
	{
		ans=min(ans,dp[n][m][i][0]);
	}
	if(ans==maxn)
		cout<<"impossible";
	else
	cout<<ans;
	
	//cout<<dp[2][4][2];
	return 0;
}