pypy3 解法, 执行用时: 84ms, 内存消耗: 75380K, 提交时间: 2022-08-05 10:43:43

n,m,h = [int(x) for x in input().split()]
mg=[]
d={'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9,'.':0,'*':999}
dirc=[(0,1),(0,-1),(1,0),(-1,0)]
for _ in range(n):
    mg.append([d[x] for x in input()])
mg2=[[[9999,0] for x in y] for y in mg]
road=[[0,0,0,h]]
res=10000
while road:
    a,b,step,h = road.pop(0)
    if a==n-1 and b==m-1 and step<res:
        res=step
        continue
    #mg2[a][b] =1
    h= h - mg[a][b]
    step = step+1
    for i in range(4):
        x = a + dirc[i][0]
        y = b + dirc[i][1]
        if x >=0 and y>=0 and x<n and y<m and (mg2[x][y][0]>step or h>mg2[x][y][1])  and h>mg[x][y]:
            mg2[x][y][0]=step
            mg2[x][y][1]=h
            road.append([x,y,step, h])

if res<10000:
    print(res)
else:
    print(-1)

C++ 解法, 执行用时: 3ms, 内存消耗: 456K, 提交时间: 2021-12-04 20:48:47

#include<bits/stdc++.h>
using namespace std;
int n,m,h,ans=100000;
bool vis[55][55];char mp[55][55];
void dfs(int x,int y,int h,int step)
{
	if(x<=0||x>n||y<0||y>=m||h<=0||mp[x][y]=='*'||vis[x][y]) return ;
	if(x==n&&y==m-1){
		ans=min(ans,step);
		return ;
	}
	 vis[x][y]=1;
	if(mp[x][y]=='.'){
		dfs(x+1,y,h,step+1);
		dfs(x-1,y,h,step+1);
		dfs(x,y+1,h,step+1);
		dfs(x,y-1,h,step+1);
	}
	else{
		int s=mp[x][y]-'0';
		dfs(x+1,y,h-s,step+1);
		dfs(x-1,y,h-s,step+1);
		dfs(x,y+1,h-s,step+1);
		dfs(x,y-1,h-s,step+1);
	}
	vis[x][y]=0;
 } 
 int main()
 {
 	cin>>n>>m>>h;
 	for(int i=1;i<=n;i++)
 	   cin>>mp[i];
 	dfs(1,0,h,0);
 	if(ans==100000) cout<<"-1"<<endl;
 	else cout<<ans<<endl;
 }