找不到BUG

P1434 [SHOI2002] 滑雪

小豆子范德萨 @ 2020-03-30 11:37:52

#include <bits/stdc++.h>
using namespace std;
int a[110][110];
int dp[110][110];       //dp[i][j]代表从i,j坐标上下左右的滑坡距离 
int dir[4][2] = {
    {-1,0},
    {1,0},
    {0,-1},
    {0,1}
};
int r,c;

bool inside(int i,int j) {      //判断边界 
    if(i < 0 || i >= r || j < 0 || j >= c) return false;
    return true;
}

int dfs(int i,int j) {  //v当前滑雪距离 
    if(dp[i][j]) return dp[i][j];
    dp[i][j] = 1;
    for(int k = 0;k < 4;k++) {
        int newi = i + dir[k][0];
        int newj = j + dir[k][1];
        if(inside(newi,newj) && a[newi][newj] < a[i][j]) {
            cout<<"newi:->"<<newi<<"newy->:"<<newj<<"\n";
            int t = dfs(newi,newj); 
            return dp[i][j] = max(dp[i][j],t+1);
        }
    }
}

int main() {
    cin>>r>>c;
    for(int i = 0;i < r;i++) {
        for(int j = 0;j < c;j++) scanf("%d",&a[i][j]);
    }

    int ans = 0;
    for(int i = 0;i < r;i++) {      //从该点出发到达的最长距离 
        for(int j = 0;j < c;j++) {
            ans = max(ans,dfs(i,j));
        }
    }
    cout<<ans;
    return 0;
}

照着题解敲得找不到bug,输出是15,不是25,求大神帮忙看下


by Ryo_Yamada @ 2020-03-30 11:51:37

@小豆子范德萨

return dp[i][j] = max(dp[i][j],t+1);

这里直接return的话下面如果有更大的答案就找不到了,应该先4种情况都取一遍max,最后再return dp[i][j];


by 小豆子范德萨 @ 2020-03-30 11:56:54

@breeze末影 谢谢,但是先dfs不是要用返回值接么?


by Ryo_Yamada @ 2020-03-30 11:58:22

@小豆子范德萨 因为你向4个方向dfs的结果不一定相同,所以需要dfs4个方向,才能保证取到最大值。


by Ryo_Yamada @ 2020-03-30 11:59:42

@小豆子范德萨 可以这么写(没测过,但应该是对的


int dfs(int i,int j) {  //v当前滑雪距离 
    if(dp[i][j]) return dp[i][j];
    dp[i][j] = 1;
    for(int k = 0;k < 4;k++) {
        int newi = i + dir[k][0];
        int newj = j + dir[k][1];
        if(inside(newi,newj) && a[newi][newj] < a[i][j]) {
            //cout<<"newi:->"<<newi<<"newy->:"<<newj<<"\n";
            int t = dfs(newi,newj); 
            dp[i][j] = max(dp[i][j],t+1);
        }
    }
    return dp[i][j];
}

by 小豆子范德萨 @ 2020-03-30 12:00:04

@breeze末影 对的,对的。谢谢大神


|