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