Description
勇敢的德鲁伊法里奥出色的完成了任务之后，正在迅速的向自己的基地撤退。但由于后面有着一大群追兵，所以法里奥要尽快地返回基地，否则就会被敌人捉住。
终于，法里奥来到了最后的一站：泰拉希尔原野，穿过这里就可以回到基地了。然而，敌人依然紧追不舍。不过，泰拉希尔的地理条件对法里奥十分有利，众多的湖泊随处分布。敌人需要绕道而行，但法里奥拥有变成鹰的特殊能力，使得他能轻轻松松的飞越湖面。当然，为了保证安全起见，法里奥还是决定找一条能最快回到基地的路。
假设泰拉希尔原野是一个m*n的矩阵，它有两种地形，P表示平地，L表示湖泊，法里奥只能停留在平地上。他目前的位置在左上角(1,1)处，而目的地为右下角的(m,n)。法里奥可以向前后左右四个方向移动或者飞行，每移动一格需要1单位时间。而飞行的时间主要花费在变形上，飞行本身时间消耗很短，所以无论一次飞行多远的距离，都只需要1单位时间。飞行的途中不能变向，并且一次飞行最终必须要降落在平地上。当然，由于受到能量的限制，法里奥不能无限制的飞行，他总共最多可以飞行的距离为D。在知道了以上的信息之后，请你帮助法里奥计算一下，他最快到达基地所需要的时间。
Input
第一行是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
4 4 2 PLLP PPLP PPPP PLLP
Sample Output
5
分析：
直接用广搜法解答即可。要注意总飞行路程为D，而不是单次的飞行路程，另外不是只越过湖水的时候才飞的，平地一样可以。本题很好的说明了广度搜索的特性，即应该搜索所有同层的可能状态，而不是人为规定同层最优解，最优解是在搜索的过程中找到的。同时注意，标记是否访问的数组维度取决于状态的复杂程度，本题中因为涉及剩余飞行路程这一变量，必须令标记数组有3个维度。毕竟，不是只要到达一个点就可以，还要考虑到达时不同的剩余飞行长度对应不同的向下搜素状态。
代码：
1 // Problem#: 1135 2 // Submission#: 1867544 3 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License 4 // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/ 5 // All Copyright reserved by Informatic Lab of Sun Yat-sen University 6 #include <iostream> 7 #include <queue> 8 #include <cstring> 9 using namespace std; 10 11 #define MAX 100 12 13 struct node{ 14 int x,y,step,remain; 15 node( int a, int b, int c,int r ){ 16 x = a; y = b; step = c; remain = r; 17 } 18 }; 19 20 bool _map[MAX][MAX]; 21 bool visit[MAX][MAX][MAX]; 22 int move[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; 23 int m,n,d; 24 25 inline bool judge( int a, int b ){ 26 return a>=0 && a<m && b>=0 && b<n; 27 } 28 29 void bfs( int m, int n, int d ){ 30 memset(visit,false,sizeof(visit)); 31 queue<node> buffer; 32 buffer.push(node(0,0,0,d)); 33 visit[0][0][d] = true; 34 while(!buffer.empty()){ 35 node tmp = buffer.front(); 36 buffer.pop(); 37 if( tmp.x == m-1 && tmp.y == n-1 ){ 38 cout << tmp.step << endl; 39 return ; 40 } 41 int a,b; 42 int c = tmp.step + 1; 43 int r = tmp.remain; 44 for( int i=0 ; i<4 ; i++ ){ 45 a = move[i][0] + tmp.x; 46 b = move[i][1] + tmp.y; 47 if( judge(a,b) && _map[a][b] && !visit[a][b][r] ){ 48 buffer.push(node(a,b,c,r)); 49 visit[a][b][r] = true; 50 } 51 for( int j=2 ; j<=r ; j++ ){ 52 a += move[i][0]; 53 b += move[i][1]; 54 if( judge(a,b) && _map[a][b] && !visit[a][b][r-j] ){ 55 buffer.push(node(a,b,c,r-j)); 56 visit[a][b][r-j] = true; 57 } 58 } 59 } 60 } 61 cout << "impossible" << endl; 62 } 63 64 int main(){ 65 char c; 66 cin >> m >> n >> d; 67 memset(_map,false,sizeof(_map)); 68 for( int i=0 ; i<m ; i++ ){ 69 for( int j=0 ; j<n ; j++ ){ 70 cin >> c; 71 if( c=='P' ) _map[i][j] = true; 72 } 73 } 74 bfs(m,n,d); 75 return 0; 76 }