这样用dfs哪里不对
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 55;
char g[N][N];
bool st[N][N][N];
int length[N][N][N];
int n,m,h;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int dp(int a, int b,int cnt)
{
// cout << a << " " << b << " " << cnt << endl;
int &v = length[a][b][cnt];
// cout << a << " " << b << " " << v <<" " << cnt << endl;
if(a == n && b == m) return 0;
if(st[a][b][cnt]) return v;
for(int i = 0; i < 4; i++)
{
int x = a + dx[i];
int y = b + dy[i];
if(x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] != '*' && !st[x][y][cnt]) {
st[a][b][cnt] = 1;
if(g[x][y] == '.') v = min(v,dp(x,y,cnt) + 1);
else if(cnt + g[x][y] - '0' < h) v = min(v,dp(x,y,cnt + g[x][y] - '0') + 1);
}
}
return v;
}
int main()
{
cin >> n >> m >> h;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> g[i][j];
memset(length,0x3f,sizeof length);
// length[1][1] = 0;
dp(1,1,0);
// cout << length[n][m];
if(length[1][1][0] == 0x3f3f3f3f) cout << "-1";
else cout << length[1][1][0];
return 0;
}
全部评论
(0) 回帖