P8673 [蓝桥杯 2018 国 C] 迷宫与陷阱 参考代码

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'

typedef long long LL;
const int maxn = 1000 + 100;
const int INF = 0x3f3f3f3f;
struct Node {
    int x, y, z;
    Node() {}
    Node(int x, int y, int z) : x(x), y(y), z(z) {}
};

int n, k;
char str[maxn][maxn];
int dis[maxn][maxn][20];
queue<Node> que;
const int dir[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};

bool in(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> str[i];
    }
    memset(dis, 0x3f, sizeof(dis));
    que.push({0, 0, 0});
    dis[0][0][0] = 0;
    while (!que.empty()) {
        Node tmp = que.front();
        que.pop();
        for (int i = 0; i < 4; ++i) {
            int x = tmp.x + dir[i][0];
            int y = tmp.y + dir[i][1];
            int z = max(tmp.z - 1, 0);
            if (!in(x, y) || str[x][y] == '#') {
                continue;
            }
            if (str[x][y] == '%') {
                z = k + 1;
            }
            if (str[x][y] == 'X') {
                if (z == 0) {
                    continue;
                }
            }
            if (dis[x][y][z] > dis[tmp.x][tmp.y][tmp.z] + 1) {
                dis[x][y][z] = dis[tmp.x][tmp.y][tmp.z] + 1;
                que.push({x, y, z});
            }
        }
    }
    int ans = INF;
    for (int i = 0; i <= k; ++i) {
        ans = min(ans, dis[n - 1][n - 1][i]);
    }
    cout << (ans == INF ? -1 : ans) << endl;

    return 0;
}