题解 | #小红的rpg游戏#

D.小红的rpg游戏

考虑dfs,当然如果单纯的dfs肯定是要超时的,但只需要剪一下枝就行了,对于步数超过已经搜寻到的最短步数的路径直接摘除即可,可以说是dfs最经典的剪枝了

code:

#include<bits/stdc++.h>
using namespace std;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
char ma[55][55];
int vis[55][55];
int n,m,h;
int ans = 0x3f3f3f3f;
void dfs(int nowx,int nowy,int nowhp,int step)//分别表示当前坐标,当前血量,当前步数
{
    if(step>ans||vis[nowx][nowy]||nowhp<=0)    return;//越界条件
    if(nowx==n&&nowy==m)
    {
        ans = min(ans,step);
        return;
    }
    vis[nowx][nowy] = 1;
    for(int i = 0;i<4;++i)
    {
        int xx = nowx+dx[i],yy = nowy+dy[i];
        if(ma[xx][yy]=='*')    continue;
        if(ma[xx][yy]=='.')    dfs(xx,yy,nowhp,step+1);
        if(ma[xx][yy]<='9'&&ma[xx][yy]>='0')    dfs(xx,yy,nowhp-ma[xx][yy]+'0',step+1);
    }
    vis[nowx][nowy] = 0;
}
int main()
{
    cin>>n>>m>>h;
    memset(ma,'*', sizeof(ma));
    for(int i = 1;i<=n;++i)
       for(int j = 1;j<=m;++j)
           cin>>ma[i][j];
    dfs(1,1,h,0);
    if(ans>=0x3f3f3f3f)    cout<<-1<<endl;
    else    cout<<ans<<endl;
    return 0;
}