题解 | 小红的rpg游戏

以当前的坐标和血量作为状态进行 BFS 即可，时间复杂度。

#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;

using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

const int INF = 0x3f3f3f3f;

int n;
int m;
int h;

vector<string> grid;

vector<vector<vector<int>>> dis;

void Solve() {
    cin >> n >> m >> h;
    grid.resize(n + 2);
    grid[0].assign(m + 2, '*');
    for (int i = 1; i <= n; i++) {
        string& row = grid[i];
        cin >> row;
        row = '*' + row + '*';
    }
    grid.back().assign(m + 2, '*');
    dis.assign(n + 1, vector<vector<int>>(m + 1, vector<int>(h + 1, INF)));
    queue<tiii> que;
    dis[1][1][h] = 0;
    que.emplace(1, 1, h);
    while (que.size()) {
        auto [x, y, z] = que.front();
        if (x == n && y == m) {
            cout << dis[x][y][z];
            return;
        }
        int newDis = dis[x][y][z] + 1;
        int dmg;
        char c;
        int k;
        for (const auto& [i, j] : {
                    pii{x - 1, y}, {x, y - 1}, {x, y + 1}, {x + 1, y}
                }) {
            c = grid[i][j];
            if (c != '*') {
                dmg = c == '.' ? 0 : c - '0';
                if (z > dmg) {
                    k = z - dmg;
                    if (dis[i][j][k] == INF) {
                        dis[i][j][k] = newDis;
                        que.emplace(i, j, k);
                    }
                }
            }
        }
        que.pop();
    }
    cout << "-1";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();
    return 0;
}