被dfs坑了 | #小红的rpg游戏#

孩子们别写

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;

const int N = 60, MOD = 998244353;
const int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
const LL INF = 1e18;

int n, m, h;
string g[N];
bool st[N][N][N];
LL d[N][N][N];
LL ans = INF;

struct F {
    int x, y;
    LL h;
};

void bfs() {
    memset(d, 0x3f, sizeof d);
    d[0][0][h] = 0;
    queue<F> q;
    q.push({0, 0, h});
    while (q.size()) {
        auto [x, y, t] = q.front();
        q.pop();
        if (x == n - 1 && y == m - 1) {
            ans = min(ans, d[x][y][t]);
        }

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (g[nx][ny] == '*') continue;
            if (g[nx][ny] == '.') {
                if (d[x][y][t] + 1 < d[nx][ny][t]) {
                    d[nx][ny][t] = d[x][y][t] + 1;
                    q.push({nx, ny, t});
                }
            }
            else {
                int v = g[nx][ny] - '0';
                int j = t - v;
                if (j <= 0) continue;
                if (d[x][y][t] + 1 < d[nx][ny][j]) {
                    d[nx][ny][j] = d[x][y][t] + 1;
                    q.push({nx, ny, t - v});
                }
            }
        }
    }
}

void solve() {
    cin >> n >> m >> h;
    for (int i = 0; i < n; ++i) cin >> g[i];

    bfs();

    if (ans == INF) ans = -1;
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();

    return 0;
}