竞赛讨论区 > 小白月赛41 e题求助

小白月赛41 e题求助

头像
牛客777172144号
发布于 2021-12-06 11:58:22 APP内打开
赞 0 | 收藏 0 | 回复0 | 浏览243
这样用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条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐