飞越原野 （经典广搜）

飞越原野

Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 60   Accepted Submission(s) : 16

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

勇敢的法里奥出色的完成了任务之后，正在迅速地向自己的基地撤退。但由于后面有着一大群追兵，所以法里奥要尽快地返回基地，否则就会被敌人逮住。     终于，法里奥来到了最后的一站；泰拉希尔草原，穿过这里就可以回到基地了。然而，敌人依然紧追不舍。不过，泰拉希尔的地理条件对法里奥十分有利，众多的湖泊随处分布。敌人需要绕道而行，但法里奥拥有变成鹰的特殊能力，使得他能轻轻松松地飞越湖面。当然，为了保证安全起见，法里奥还是决定找一条能最快回到基地的路。     假设泰拉希尔草原是一个m*n的矩阵，它有两种地形，P表示平地，L表示湖泊，法里奥只能停留在平地上。他目前的位置在左上角(1,1)处，而目的地为右下角的(m,n)。法里奥可以向前后左右4个方向移动或飞行，每移动1格需要1单位时间。而飞行的时间主要花费在变形上，飞行本身时间消耗很短，所以无论一次飞行多远的距离，都只需要1单位时间。飞行的途中不能变向，并且一次飞行最终必须要降落在平地上。当然，由于受到能量的限制，法里奥不能无限制的飞行，他总共最多可以飞行的距离为D。在知道了以上的信息之后，请你帮助法里奥计算一下，他最快到达基地所需的时间。

Input

第1行为测试示例的个数，每个测试示例的第1行是3个正整数，m(1<=m<=100)，n(1<=n<=100)，D(1<=D<=100)。表示原野是m*n的矩阵，法里奥最多只能飞行距离为D。 接下来的m行每行有n个字符，相互之间没有空格。P表示当前位置是平地，L则表示湖泊。假定(1,1)和(m,n)一定是平地。

Output

对于每个测试示例输出一个整数，表示法里奥到达基地需要的最短时间。如果无法到达基地，则输出impossible。

Sample Input

1
4 4 2
PLLP
PPLP
PPPP
PLLP

Sample Output

5

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<queue>

//#include<windows.h>

using namespace std;

#define maxn 110

typedef struct Node

{

      int x,y;

      int step;

      int dist;

}Node;

int n,m,D;

int dx[4]={1,0,-1,0};

int dy[4]={0,1,0,-1};

int step[maxn][maxn],dist[maxn][maxn];

char map[maxn][maxn];

int cango(Node next)

{

      if(next.x<1||next.x>n) return 0;

      if(next.y<1||next.y>m) return 0;

      ////if(map[next.x][next.y]=='L') return 0;/////害死人了

      return 1;

}

int bfs()

{

      int i,j;

      Node tmp,next;

      memset(step,0,sizeof(step)); memset(dist,0,sizeof(dist));

      tmp.x=1,tmp.y=1,tmp.dist=D,tmp.step=0,dist[1][1]=D,step[1][1]=0;

      queue<Node>Q;

      Q.push(tmp);

      while(!Q.empty())

      {

           Node tmp;

           tmp=Q.front(),Q.pop();

           for(i=0;i<4;i++)

           {

                 next.x=tmp.x+dx[i],next.y=tmp.y+dy[i];

                 if(!cango(next)) continue;//////有时候用函数也是有害处的，

                 if(map[next.x][next.y]!='L')

                 {

                      /*找到返回*/

                      if(next.x==n&&next.y==m) return tmp.step+1;

                      /*用步走*/

                      if(step[next.x][next.y]>0)

                      {

                            if(tmp.step+1<step[next.x][next.y]||tmp.dist>dist[next.x][next.y])

                            {

                                  next.step=tmp.step+1;  step[next.x][next.y]=tmp.step+1;

                                  next.dist=tmp.dist;    dist[next.x][next.y]=tmp.dist;

                                 

                                  Q.push(next);

                            }/*

                            else if(tmp.dist>next.dist)

                            {

                                  next.step=tmp.step+1;

                                  next.dist=tmp.dist;

                                  Q.push(next);

                            }*/

                      }

                      else if(dist[next.x][next.y]<D) //防止把原点(1,1,0,D)放进去 ,不加if时把原点放进去了，调试了好久（两个晚上，伤不起）；

                      {

                            next.step=tmp.step+1; step[next.x][next.y]=tmp.step+1;

                            next.dist=tmp.dist;  dist[next.x][next.y]=tmp.dist;

               

                            Q.push(next);

                      }

                 }

                 /*飞行*/

                 for(j=2;j<=tmp.dist;j++)

                 {

                      int d=tmp.dist-j;

                      next.x=tmp.x+j*dx[i],next.y=tmp.y+j*dy[i];

                      if(!cango(next)) break;

                      if(map[next.x][next.y]=='L') continue;

                      if(next.x==n&&next.y==m) return tmp.step+1;

                if(step[next.x][next.y]==0&&dist[next.x][next.y]<D||tmp.step+1<step[next.x][next.y]||d>dist[next.x][next.y])

                      {

                            next.step=tmp.step+1; step[next.x][next.y]=tmp.step+1;

                          next.dist=d;  dist[next.x][next.y]=d;

                            Q.push(next);

                      }

                 }

           }

      }

      //printf("ERROR!\n");//////调试

      return 0;

}

int main()

{

      //freopen("input.txt","r",stdin);

//   DWORD take=GetTickCount();

      int i,j,T;

    scanf("%d",&T);

    while(T--)

      {

           scanf("%d%d%d\n",&n,&m,&D);

           for(i=1;i<=n;i++)

                 for(j=1;j<=m;j++)

                      if(j==m) scanf("%c\n",&map[i][j]);

                      else scanf("%c",&map[i][j]);

           /*

           for(i=1;i<=n;i++)

           {

                 for(j=1;j<=m;j++) printf("%c",map[i][j]);

                 printf("\n");

           }*/

           int t=bfs();

           if(t) printf("%d\n",t);

           else printf("impossible\n");

      }

      //printf("%d\n",GetTickCount()-take);

      return 0;

}