题解：P9351 [JOI 2023 Final] Maze

2huk · 2024-08-16 22:35:01 · 题解

太摆了丢个代码跑路：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e7 + 10;

vector<vector<bool>> g;

int n, m, k, sx, sy, tx, ty;
vector<vector<bool>> st;
vector<vector<int>> dis;

const int dx[] = {0, 1, 0, -1, -1, -1, 1, 1}, dy[] = {1, 0, -1, 0, -1, 1, -1, 1};

bool chk(int x, int y) {
    return x >= 1 && y >= 1 && x <= n && y <= m;
}

struct Node {
    int x, y, cost, r;

    bool operator >(const Node& h) const {
        return cost == h.cost ? r < h.r : cost > h.cost;
    }
};

void bfs(int x, int y) {
    st.resize(n + 2);
    dis.resize(n + 2);
    for (int i = 1; i <= n; ++ i ) {
        st[i].resize(m + 2);
        dis[i].resize(m + 2);
    }

    for (int i = 1; i <= n; ++ i )
        for (int j = 1; j <= m; ++ j ) {
            st[i][j] = false;
            dis[i][j] = 1e9;
        }

    priority_queue<Node, vector<Node>, greater<Node>> q;
    q.push({x, y, 0, 0});
    dis[x][y] = 0;

    while (q.size()) {
        int x = q.top().x, y = q.top().y, r = q.top().r;
        q.pop();

        if (st[x][y]) continue;
        st[x][y] = true;

        if (!r) {
            for (int i = 0; i < 4; ++ i ) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (chk(nx, ny) && dis[nx][ny] > dis[x][y] + g[nx][ny]) {
                    dis[nx][ny] = dis[x][y] + g[nx][ny];
                    q.push({nx, ny, dis[nx][ny], g[nx][ny] ? k - 1 : 0});
                }
            }
        }
        else {
            for (int i = 0; i < 8; ++ i ) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (chk(nx, ny) && dis[nx][ny] > dis[x][y]) {
                    dis[nx][ny] = dis[x][y];
                    q.push({nx, ny, dis[nx][ny], r - 1});
                }
            }
        }
    }

    return;
}

int main() {
//  freopen("maze4.in", "r", stdin);
//  freopen("maze.out", "w", stdout);

    cin >> n >> m >> k >> sx >> sy >> tx >> ty;

    g.resize(n + 2);
    for (int i = 1; i <= n; ++ i ) {
        g[i].resize(m + 2);
        for (int j = 1; j <= m; ++ j ) {
            char c;
            cin >> c;
            g[i][j] = c == '#';
        }
    }

    bfs(sx, sy);
    cout << dis[tx][ty] << '\n';

    return 0;
}