1.贼好的一道题：
题目：https://ac.nowcoder.com/acm/contest/11218/E?&headNav=acm

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

typedef pair<int,int>PII;
typedef pair<PII,PII>PIPI;  //{x,y,dist,hp}
const int N = 55;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
char g[N][N];
bool vis[N][N][N];
int n, m, h;

int bfs(){
    queue<PIPI>q;
    q.push({{0, 0}, {0, h}});
    while(q.size()){
        PIPI u = q.front();
        q.pop();
        PII l = u.first, r = u.second;
        int dist = r.first, hp = r.second;
        for(int i = 0; i < 4; i ++ ){
            int a = l.first + dx[i], b = l.second + dy[i];
            if(a >= 0 && b >= 0 && a < n && b < m && !vis[a][b][hp] && g[a][b] != '*'){
                vis[a][b][hp] = true;
                if(a == n - 1 && b == m - 1)    return dist + 1;
                if(g[a][b] == '.')  q.push({{a, b}, {dist + 1, hp}});
                else{
                    int rest_hp = hp - (g[a][b] - '0');
                    if(rest_hp > 0) q.push({{a, b}, {dist + 1, rest_hp}});
                }
            }
        }
    }
    return -1;
}

int main(){
    cin>>n>>m>>h;
    for(int i = 0; i < n; i ++ )    cin>>g[i];
    int val = bfs();
    cout<<val;
    return 0;
}