题解 | 小红的rpg游戏

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};

struct state {
    int x, y, hp, dist;
};

int main(){
int n,m,h;
cin>>n>>m>>h;
vector<string>v(n);
for(int i=0;i<n;i++){
    cin>>v[i];
}
vector<vector<vector<int>>>vit(n,vector<vector<int>>(m,vector<int>(51)));
queue<state>q;
q.push({0,0,h,0});
while(!q.empty()){
    auto it=q.front();
    q.pop();
    int x=it.x;
    int y=it.y;
    int hp=it.hp;
    int dist=it.dist;
    if(x==n-1&&y==m-1){
        cout<<dist;
        return 0;
    }
    for(int i=0;i<4;i++){
        int xn=x+dx[i];
        int yn=y+dy[i];
        if(xn<0||xn>=n||yn<0||yn>=m)continue;
        if(v[xn][yn]=='*')continue;
        if(v[xn][yn]>='0'&&v[xn][yn]<='9'){
int hn=v[xn][yn]-'0';
if(hp<=hn)continue;
else{
    if(vit[xn][yn][hp-hn]==0){
    q.push({xn,yn,hp-hn,dist+1});
    vit[xn][yn][hp-hn]=1;
    }
}


        }
        if(v[xn][yn]=='.'){
    if(vit[xn][yn][hp]==0){
        q.push({xn,yn,hp,dist+1});
        vit[xn][yn][hp]=1;
    }
}
    }

}

cout<<-1;


    return 0;
}