求解,求大佬解释

P1434 [SHOI2002] 滑雪

wansaa @ 2023-04-04 20:42:02

在main函数里面那个dfs要处理所有的节点呀

#include<stdio.h>
int map[105][105],r,c;
int m1[4]={1,0,-1,0};
int m2[4]={0,-1,0,1};
int maxd[105][105];
int maxlen;
int maxnum(int a,int b)
{
    return a>b?a:b;
}
int check(int a,int b)
{
    return a>0&&a<=r&&b>0&&b<=c;
}
int dfs(int x,int y)
{
    if(maxd[x][y]) return maxd[x][y];
    maxd[x][y]=1;
    for(int i=0;i<4;i++)
    {
        if(check(x+m1[i],y+m2[i])&&map[x][y]>map[x+m1[i]][y+m2[i]])
        {
            maxd[x][y]=maxnum(dfs(x+m1[i],y+m2[i])+1,maxd[x][y]);
        }
    }
    return maxd[x][y];
}
int main()
{
    scanf("%d %d",&r,&c);
    int max=0,mr=1,mc=1;
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            scanf("%d",&map[i][j]);
        }
    }
    for(int i=1;i<=r;i++)//为啥要用两层for循环
    {
        for(int j=1;j<=c;j++)
        {
            maxlen=maxnum(maxlen,dfs(i,j));
        }
    }
    printf("%d",maxlen);
    return 0;
}

by leoqing @ 2023-04-04 21:15:11

遍历数组中每一个值呀(你写的你咋会不知道呢)


by wansaa @ 2023-04-04 22:06:20

@leoqing 遍历数组中每个值是为了什么,难道一次dfs只能得到从这个节点出发的最长路径吗


by pxlamda @ 2023-04-20 10:33:05

@wansaa 我的理解是dfs把所有的点都访问过一次就能保证最长的路径,有可能前两个点就做到了,但是每次dfs都要检查所有的点有没有都被访问太费时间了,还不如每个点都dfs


|