题解 | 小红的rpg游戏

使用BFS

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

struct State{
    int x,y,hp;
    int step;
    State(int x_,int y_,int hp_,int step_):x(x_),y(y_),hp(hp_),step(step_){}
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,h;
    cin>>n>>m>>h;
    vector<string>maze(n);
    for(int i=0;i<n;i++){
        cin>>maze[i];
    }
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,-1,1};
    bool vis[50][50][51]={false};
    queue<State>q;
    q.push(State(0,0,h,0));
    vis[0][0][h]=true;
    int res=-1;
    while(!q.empty()){
        State curr=q.front();
        q.pop();
        if(curr.x==n-1&&curr.y==m-1){
            res=curr.step;
            break;
        }
        for(int i=0;i<4;i++){
            int x=curr.x+dx[i];
            int y=curr.y+dy[i];
            if(x<0||x>=n||y<0||y>=m)continue;
            if(maze[x][y]=='*')continue;
            int new_hp=curr.hp;
            if(isdigit(maze[x][y])){
                int harm=maze[x][y]-'0';
                if(new_hp<=harm)continue;
                new_hp-=harm;
            }
            if(!vis[x][y][new_hp]){
                vis[x][y][new_hp]=true;
                q.push(State(x,y,new_hp,curr.step+1));
            }
        }
    }
    cout<<res<<endl;
    return 0;
}