勇敢的法里奥出色的完成了任务之后，正在迅速地向自己的基地撤退。但由于后面有着一大群追兵，所以法里奥要尽快地返回基地，否则就会被敌人逮住。
终于，法里奥来到了最后的一站:泰拉希尔原野，穿过这里就可以回到基地了。然而，敌人依然紧追不舍。不过，泰拉希尔的地理条件对法里奥十分有利，众多的湖泊随处分布。敌人需要绕道而行，但法里奥还是决定找一条能尽快回到基地的路。
假设泰拉希尔原野是一个m*n的矩阵，它有两种地形，P表示平，L表示湖泊，法里奥只能停留在平地上。他目前的位置在左上角（1，1）处，而目的地为右下角的（m，n）。法里奥可以向前后左右4个方向移动或飞行，每移动1格需要1单位时间。而飞行的时间主要花费在变形上，飞行本身时间消耗很短，所以无论一次飞行多远的距离，都只需要1单位时间。飞行的途中不能变向，并且一次飞行最终必须要降落到平地上。当然，由于受到能量的限制，法里奥不能无限制飞行，他总共最多可以飞行的距离为D。在知道了以上的信息之后，请你帮助法里奥计算一下，他最快到达基地所需要的时间。
第一行是3个整数，m（1≤m≤100），n（1≤n≤100），D（1≤D≤100）。表示原野是m*n的矩阵，法里奥最多只能飞行距离为D。接下来的m行每行有n个字符，相互之间没有空格。P表示当前位置是平地，L则表示湖泊。假定（1，1）和（m，n）一定是平地。
一个整数，表示法里奥到达基地需要的最短时间。如果无法到达基地，则输出impossible。
节点记录状态，那都需要保存什么信息呢？记录当前的x,y坐标，所用时间，剩余的可飞行距离。
判重和一般的BFS不同，开一个三维的数组bool inq[105][105][105];记录走过的路径，因为需要额外的维度来记录剩余的飞行能力。因为，同样是到达一个点，不同的飞行剩余距离，所得答案有可能不同。
利用BFS进行搜索，和一般的BFS不同的是，每一个结点扩展出来的孩子结点既有行走的，也有飞行的。所以，既需要枚举4个方向走一步的情况，也需要枚举朝4个方向飞行2格、3格···一直到最大剩余飞行距离。
#include<iostream> #include<algorithm> #include<string> #include<cstdio> #include<cstring> #include<cmath> #include<stack> #include<queue> using namespace std; typedef long long ll; const int MOD = 10000007; const int INF = 0x3f3f3f3f; const double PI = acos(-1.0); const int maxn = 300; int n,m,d; char a[105][105]; bool inq[105][105][105]; int X[4] = {-1, 1, 0, 0}; int Y[4] = {0, 0, -1, 1}; struct node { int x, y; //记录坐标 int t; //记录所用的时间 int dis; //剩余可飞行的距离 }start, top, tmp; bool judge(int x, int y, int dis) { if(x<1||x>m||y<1||y>n) return false; if(inq[x][y][dis]==true) return false; if(a[x][y]=='L') return false; return true; } int BFS() { queue<node> q; start.x = 1; start.y = 1; start.t = 0; start.dis = d; q.push(start); inq[start.x][start.y][start.dis] = true; while(!q.empty()) { top = q.front(); q.pop(); if(top.x==m&&top.y==n) return top.t; for(int i = 0; i < 4; i++) //向四个方向行走 { int newx = top.x + X[i]; int newy = top.y + Y[i]; if(judge(newx, newy, top.dis)) { tmp.x = newx; tmp.y = newy; tmp.t = top.t + 1; //多消耗一个单位的时间 tmp.dis = top.dis; //剩余可飞行的距离不变 q.push(tmp); inq[tmp.x][tmp.y][tmp.dis] = true; } } for(int j = 2; j <= top.dis; j++)//向四个方向飞行j格，两格、三格……最大直到剩余可飞行的距离 { for(int i = 0; i < 4; i++) { int newx = top.x + X[i]*j; int newy = top.y + Y[i]*j; if(judge(newx, newy, top.dis-j)) { tmp.x = newx; tmp.y = newy; tmp.t = top.t + 1; //多消耗一个单位的时间 tmp.dis = top.dis - j; //剩余可飞行的距离减少j q.push(tmp); inq[tmp.x][tmp.y][tmp.dis] = true; } } } } return -1; } int main() { //解除的是C++运行库层面的对数据传输的绑定，取消输入输出时数据加入缓存，以提高效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>m>>n>>d; for(int i = 1; i <= m; i++) for(int j = 1; j <= n;j++) cin>>a[i][j]; int flag = BFS(); if(flag==-1) cout<<"impossible"<<endl; else cout<<flag<<endl; return 0; }