题意：
机器人要从一个m*n（1<=m,n<=20）网格的左上角（1,1）到右下角（m,n）。网格中的一些格子是空地（用0表示），其他格子是障碍（用1表示）。机器人每次可以往四个方向走一格，但不能连续穿越k个（0<=K<=20）障碍，求最短的长度。起点和终点保证是空地。如图：最短的长度是10.
Input
The input consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.
For each data set, the first line contains two positive integer numbers m and n separated by space (1m, n
20). The second line contains an integer number k(0
k
20). The ith line of the next m lines contains n integer aij separated by space (i = 1, 2,..., m;j = 1, 2,...,n). The value of aij is 1 if there is an obstacle on the cell (i, j), and is 0 otherwise.
Output
For each data set, if there exists a way for the robot to reach the cell (m, n), write in one line the integer number s, which is the number of moves the robot has to make; -1 otherwise.
Sample Input
3 2 5 0 0 1 0 0 0 0 0 0 1 0 4 6 1 0 1 1 0 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0 1 1 1 0 0 2 2 0 0 1 1 0
Sample Output
7 10 -1
思路分析：
寻找最优解，采用BFS。
前提准备：
1、首先输入的K值就是机器人的血量，连续穿越K+1个障碍之后，机器人就会挂掉。然而如果第一次连续穿越了
K-1个障碍后又遇到0，那么就要给机器人加满血。
2、用一个三维数组来标记机器人来过这里，可赋值为1。第三维的数据用机器人走这条路剩余的血量表示。
3、用队列存储每一个结点，（即每一个中心，因为机器人每到达一个地方（中心）就有四个方向可走）
分析：
1、模拟机器人巡逻，碰到“1”就减血量。
2、每到达一个点，需要判断：点是否越界（就要换方向），点是否是终点（直接结束），点是否之前来过（换方向）
3、把可以走的点存进队列，继续上面的过程。
源代码：
1 #include<iostream> 2 #include<queue> 3 #include<cstring> 4 #define MAXN 25 5 using namespace std; 6 int to[4][2] = { -1, 0, 0, -1, 1, 0, 0, 1 }; 7 int n, m, z; 8 int chess[MAXN][MAXN]; 9 int dot[MAXN][MAXN][MAXN]; 10 struct node{ 11 int x; 12 int y; 13 int z; 14 int step; 15 }R,R1,t; 16 int judge(int a, int b) 17 { 18 if (a >= n || a < 0 || b >= m || b < 0 ) 19 return 1; 20 return 0; 21 22 } 23 int bfs() 24 { 25 queue<node>Q; 26 R.x = 0; 27 R.y = 0; 28 R.z = z; 29 R.step = 0; 30 dot[0][0][z] = 1; 31 Q.push(R); 32 while (!Q.empty()) 33 { 34 t = Q.front(); 35 Q.pop(); 36 if (t.x == n - 1 && t.y == m - 1) //到达目的地 37 return t.step; 38 for (int i = 0; i < 4; i++) 39 { 40 R1.x = t.x + to[i][0]; 41 R1.y = t.y + to[i][1]; //* 之前是[0][i] 42 43 if (R1.x == n - 1 && R1.y == m - 1) 44 return t.step + 1; 45 if (judge(R1.x, R1.y)) //判断越界，越界就换方向 46 continue; 47 48 if (chess[R1.x][R1.y]) //*之前是dot[][] 49 R1.z = t.z - 1; //* 之前是z-1 ，减一表示机器人的血量 50 else 51 R1.z = z; 52 if (R1.z < 0) 53 continue; 54 if (dot[R1.x][R1.y][R1.z]) //*之前这句放在了越界的地方是错的，那里的Z还没赋值 55 continue; //判断机器人走过，就换方向 56 dot[R1.x][R1.y][R1.z] = 1; //标记机器人走过这里 57 R1.step = t.step + 1; //* 58 Q.push(R1); 59 60 } 61 62 if (Q.empty()) //*之前放在了循环里 63 { 64 65 t.step = -1; 66 return t.step; 67 } 68 } 69 } 70 int main() 71 { 72 int t; 73 cin >> t; 74 while (t--) 75 { 76 memset(chess, 0, sizeof(chess)); 77 memset(dot, 0, sizeof(dot)); 78 cin >> n >> m; 79 cin >> z; 80 for (int i = 0; i < n; i++) 81 { 82 for (int j = 0; j < m; j++) 83 cin >> chess[i][j]; 84 } 85 cout << bfs() << endl; 86 87 88 } 89 return 0; 90 }
心得：
这是第二次用BFS，不做不知道，做了才发现上一次对BFS的理解还不是很深刻，进而导致代码中出现了各种错误（*标记处），头文件也会忘记，cstring。这次做完这个题目，认真看了遍，比上次理解得更深刻了，用BFS要注意初始化，越界问题，定义的变量多少的问题，还有就是哪些变量跟着哪个点走，当然还有清零的问题。这次发现的问题比较多，总之加油吧！