飛躍原野
Time Limit: 5000ms Memory limit: 65536K 有疑問？點這裡^_^
題目描述
勇敢的法裡奧出色的完成了任務之後，正在迅速地向自己的基地撤退。但由於後面有著一大群追兵，所以法裡奧要盡快地返回基地，否則就會被敵人逮住。
終於，法裡奧來到了最後的一站:泰拉希爾原野，穿過這裡就可以回到基地了。然而，敵人依然緊追不捨。不過，泰拉希爾的地理條件對法裡奧十分有利，眾多的湖泊隨處分布。敵人需要繞道而行，但法裡奧還是決定找一條能盡快回到基地的路。
假設泰拉希爾原野是一個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。
示例輸入
4 4 2
PLLP
PPLP
PPPP
PLLP
示例輸出
5
簡單的三維BFS
手殘，WA了好幾次，就是沒發現t.d 寫成 f.d
還有 題意理解錯了，跪了一會，不一定非是湖泊才能飛，平原也可以飛
#include
#include
#include
#include
#include
const int N = 200;
using namespace std;
int mapp[N][N];
bool vis[N][N][N];
int n,m,D;
int mv[4][2] = {{1,0},{0,-1},{0,1},{-1,0}};
struct node
{
int x,y,ans,d;
};
int st(int x,int y)
{
return x*y;
}
int BFS(int D)
{
node f,t;
queueq;
memset(vis,0,sizeof(vis));
f.x = 0; f.y = 0; f.ans = 0; f.d = D;
q.push(f);
vis[f.x][f.y][f.d] = true;
while(!q.empty())
{
t = q.front();
if(t.x==n-1 && t.y==m-1)
return t.ans;
q.pop();
for(int i = 0;i < 4;i++) //走路
{
f.x = t.x + mv[i][0];
f.y = t.y + mv[i][1];
if(0 <= f.x && f.x=1;num--)//找當前最優路線，盡可能的飛的最遠
{
f.x = t.x + st(mv[i][0],num);
f.y = t.y + st(mv[i][1],num);//注意平原陸地都可以飛，但是起飛點和落地點必須都是平原
if(0 <=f.x && f.x
5 5 4
PPPPP
PPPPP
LLLLL
LLLLL
LLLLL
impossible
6 6 5
PPPPPL
PLPLPL
LLLLLL
PPPPPP
PPPPPP
PPPPPP
6
1 1 1
P
0
3 3 3
PPP
PPP
PPP
3
4 4 4
PLPL
LPLP
PPPP
LLLP
4
8 8 1
PPPPPPPP
PLPLPLPL
LLLLLLLL
PPPPPPPP
PPPPPPPP
PPPPPPPP
PPPPPPPP
PPPPPPPP
impossible
