SDUT 1124-飛躍原野--三維BFS
飛躍原野
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
QAQ用二維的bfs怒搜8個方向就是過不去，Wjj說是要狀態同步只能用三維，sad 還是對三維比較不敏感，沒往那方面想。
這道題，以行和列為x，y，以飛行距離D為z 建立三維搜索思想，然後每次在4個方向分別讓它行走和飛行。其他的沒什麼了。
#include //BFS
#include
#include
#include
#include
using namespace std;
char ma[110][110];
bool vis[110][110][110];
typedef struct node
{
int x,y,d,time;
};
int n,m,d;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void bfs()
{
queue Q;
node t;int i,j;
t.x=0;t.y=0;t.time=0;t.d=d;
Q.push(t);
while(!Q.empty())
{
node v=Q.front(); Q.pop();
if(v.x==m-1&&v.y==n-1)
{
cout<=0&&t.x=0&&t.y=0&&t.x=0&&t.y>m>>n>>d)
{
memset(vis,0,sizeof(vis));
for(i=0;i>ma[i];
bfs();
}
return 0;
}
