题解 | 2024_打怪救公主_1711类似dijkstra算法

#include<iostream>
#include<queue>

using namespace std;

struct State {
    int x, y, hp;

    bool operator<(const State &other) const {
        return hp < other.hp;
    }

    State(int x, int y, int hp) : x(x), y(y), hp(hp) {}
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int m, n, t;
    cin >> m >> n >> t;
    char matrix[m][n];
    int x1, y1, x2, y2;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
            if (matrix[i][j] == '*') {
                x1 = i;
                y1 = j;
            } else if (matrix[i][j] == '+') {
                x2 = i;
                y2 = j;
            }
        }
    }
    vector<vector<int>> max_hp(m, vector<int>(n));
    max_hp[x1][y1] = t;
    int directions[4][2] = {{-1, 0},
                            {1,  0},
                            {0,  -1},
                            {0,  1}};
    priority_queue<State> pq;
    pq.emplace(x1, y1, t);
    while (!pq.empty()) {
        State cur = pq.top();
        pq.pop();
        int x = cur.x, y = cur.y, hp = cur.hp;
        if (hp < max_hp[x][y]) continue;
        for (const auto[dx, dy]:directions) {
            int new_hp = hp;
            int nx = x + dx, ny = y + dy;
            if (nx < 0 || nx >= m || ny < 0 || ny >= n || matrix[nx][ny] == '#') continue;
            if (matrix[nx][ny] >= '0' && matrix[nx][ny] <= '9') new_hp -= matrix[nx][ny] - '0';
            if (new_hp > max_hp[nx][ny]) {
                max_hp[nx][ny] = new_hp;
                pq.emplace(nx, ny, new_hp);
            }
        }
    }
    cout << max_hp[x2][y2] << endl;
    return 0;
}