记录编号	159437	评测结果	AAAAWWAEAA
题目名称	飞越原野	最终得分	70
用户昵称	ggwdwsbs	是否通过	未通过
代码语言	C++	运行时间	0.343 s
提交时间	2015-04-21 14:40:00	内存使用	4.25 MiB

#include<stdio.h>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=101;
const int INF=2147483600;
struct nodee
{
	int x,y,stap,d;
};
int vis[maxn][maxn][maxn];
char map[maxn][maxn];
int dx[5]={0,0,1,0,-1};
int dy[5]={0,-1,0,1,0};
int n,m,d;
bool pd(int x,int y)
{
	if(x>0&&x<=n&&y>0&&y<=n&&map[x][y]=='P') return 1;
	else return 0;
} 
int bfs()
{
	memset(vis,0,sizeof(vis));
	queue<nodee>q;
	q.push((nodee){1,1,0,d});
	vis[0][0][d]=1;
	while(q.size()>0)
	{
		nodee u=q.front();
		q.pop();
		if(u.x==m&&u.y==n) 
		{
			printf("%d",u.stap);
			return 0;
		}
		int c=u.stap+1;
		for(int i=1;i<=4;i++)
		{
			int x=u.x+dx[i];
			int y=u.y+dy[i];
			if(!vis[x][y][u.d]&&pd(x,y)) 
			{
				q.push((nodee){x,y,c,u.d});
				vis[x][y][u.d]=1;
			}
			for(int j=2;j<=u.d;j++)
			{
				x+=dx[i];
				y+=dy[i];
				if(pd(x,y))
				if(!vis[x][y][u.d-j])
				{
					q.push((nodee){x,y,c,u.d-j});
					vis[x][y][u.d-j]=1;
				}
			}
		}
	}
	printf("impossible\n");
}
int main()
{
	freopen("escapea.in","r",stdin);
	freopen("escapea.out","w",stdout);
	scanf("%d%d%d",&n,&m,&d);
	for(int i=1;i<=m;i++)
	 for(int j=1;j<=n;j++)
	 {
	 	char c=getchar();
	 	while(c!='L'&&c!='P') c=getchar();
	 	map[i][j]=c;
	 }
	bfs(); 
}