算法竞赛入门经典177页，bfs，经典
题目意思：
有一个 n * m 大小的矩阵， 矩阵 只要数字 0 或者 1，0 表示空白可以走，1 表示有障碍物。
现在，要求 从起点 s(1, 1) 走到终点 t (n, m), 这两点都是空白。 每次走，可以连续穿过 k 个障碍物。
问，从 s(1, 1) 到 t (n, m) 至少走多少步。
本题要点：
1、这里的 “连续穿过 k 个障碍物” , 不一定是只要沿着一个方向走，这里的走可以是拐弯的走法。
所谓的拐弯，比如，从 点 (1, 1) ，右，下，下，左，就到达了点(3, 1)
2、如果没有k的限制，就是 bfs 的水题。加了限制，可以在原来二维 的vis数组加上第3维 layer。
vis[x][y][layer] 表示到达这一点 (x, y)，已经连续穿过了layer个1。
首先，layer > 0 的时候，表示当前点(x, y) 是 mp[x][y] 是 1（如果 当前点是 0， 那么 layer 只能是 0）;
vis[x][y][layer] == false, 进入到 点 (x, y) ， 表示 从 之前的某点（假设点 (x0, y0)）， 连续走了 layer 个 1， 才走到 点(x0, y0)。
3、 vis[x][y][layer] == true, 就不需要进入这点了。 已经有的点 （叫做 “早点” 吧） ， “早点” 更早就进入队列了，
并且尝试了 连续走了 layer 个1 才走到了点 (x, y)。
所以，其他的点 连续走了 layer 个1 才走到了点 (x, y)， 就不要再走了，因为有 “早点” 已经尝试过 了。
4、 代码是这位老哥的 点这里
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int MaxN = 25;
int n, m, k, T;
bool vis[MaxN][MaxN][MaxN];
int dx[4] = {
1, 0, -1, 0};
int dy[4] = {
0, 1, 0, -1};
int mp[MaxN][MaxN];
int cnt;struct node
{
int x, y;int step;int layer;node(int _x = 1, int _y = 1, int _step = 0, int _layer = 0):x(_x), y(_y), step(_step), layer(_layer){
}
};bool check(int x, int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}void bfs()
{
queue<node> q;memset(vis, false, sizeof vis);node s(1, 1, 0, 0);node t(n, m);q.push(s);vis[1][1][0] = true;while(!q.empty()){
node now = q.front();q.pop();if(now.x == t.x && now.y == t.y){
printf("%d\n", now.step);return;}int x, y, layer;for(int i = 0; i < 4; ++i){
x = now.x + dx[i], y = now.y + dy[i], layer = now.layer;if(mp[x][y]){
layer++;}else{
layer = 0;}if(layer <= k && check(x, y) && !vis[x][y][layer]){
q.push(node(x, y, now.step + 1, layer));vis[x][y][layer] = true;}}}printf("-1\n");
}int main()
{
scanf("%d", &T);while(T--){
scanf("%d%d%d", &n, &m, &k);for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j){
scanf("%d", &mp[i][j]); }bfs();}return 0;
}/* 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 *//* 7 10 -1 */