1600 - Patrol Robot

大致题意：机器人要从一个m*n（m和n的范围都在1到20的闭区间内）的网格的左上角（1,1）走到右下角（m，n）。网格中的一些格子是空地，用0表示，其它格子是障碍，用1表示。机器人每次可以往四个方向走一格，但不能连续地穿越k（ [0，20] ）个障碍，求最短路长度。起点和终点保证是空地。

思路：用bfs搜索即可，由于不能连续地穿越k个障碍，所以在原本的visited 2维数组上面再添加1维，变成3维数组，表示穿越的墙的层数(障碍)。

另外，以前要记录从起点走出的步数时用的是二维数组，但可以直接将step作为point结构体的一个成员变量，在将新的点加入队列时把step设置成上一个点的step+1即可，会方便一点。

// bfs中每次由扩展的结点向外探索时，四个方向分别代表了四条不同的路径
// 而连续走过的障碍的个数，这是每一条路径所特有的属性，不能作为所有路径的公有属性来保存
// 因此需要给visited数组多加一维表示不同的连续走过个数
// 而且要给每个point都保存连续走过的障碍个数这一属性，以便在某一路径中记录连续走过的障碍个数
// 和与最大限制个数进行比较

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

struct point {
    int x;
    int y;
    int step;
    int layer;
    
    point(int x, int y, int step, int layer) : x(x), y(y), step(step), layer(layer) {}
};

const int maxn = 22;

int maze[maxn][maxn];
int step[maxn][maxn];
bool visited[maxn][maxn][maxn];

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

int t;
int m, n;
int k;

int bfs() {
    queue<point> q;
    q.push(point(0, 0, 0, 0));
    int kk = 0;
    while (!q.empty()) {
        point p = q.front();
        q.pop();
        if (p.x == m - 1 && p.y == n - 1) {
            return p.step;
        }
        for (int i = 0; i < 4; i++) {
            int dx = p.x + dr[i];
            int dy = p.y + dc[i];
            int layer = p.layer;
            if (maze[dx][dy] == 1) {
                layer++;
            }
            else {
                layer = 0;
            }
            if (dx >= 0 && dx < m && dy >= 0 && dy < n && layer <= k && !visited[dx][dy][layer]) {
                q.push(point(dx, dy, p.step + 1, layer));
                visited[dx][dy][layer] = true;
            }
        }
    }
    return -1;
}

int main() {
    cin >> t;
    while (t--) {
        memset(visited, false, sizeof(visited));
        cin >> m >> n;
        cin >> k;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cin >> maze[i][j];
            }
        }
        int ans = bfs();
        cout << ans << endl;
    }
    return 0;
}