crzcqh @ 2023-07-10 08:20:53
我也知道内存可能会过大,MLE,但不知道怎么解决。
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[105][105],f[105][105]/*记忆化背包,也相当于记录每个点的答案*/,ans;
void dfs(int x,int y,int s){
if(x<1||x>n||y<1||y>m) return;
if(a[x][y]<s) return ;
if(f[x][y]) return ;
dfs(x+1,y,a[x][y]);
dfs(x-1,y,a[x][y]);
dfs(x,y+1,a[x][y]);
dfs(x,y-1,a[x][y]);//搜索四个方向
f[x][y]=max(
max(f[x+1][y],f[x-1][y]),
max(f[x][y+1],f[x][y-1])
)+1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){//每个店都做起始点遍历一遍。
dfs(i,j,a[i][j]);
ans=max(f[i][j],ans);
}
}
cout<<ans;
return 0;
}
by Vocaloid世末歌者 @ 2023-07-10 08:25:36
@crzcqh 看着没问题啊,mle可能是dfs栈炸了
by crzcqh @ 2023-07-10 09:11:48
@CPlusPlusOnMars 那怎么办呢?
by LionBlaze @ 2023-07-10 09:45:08
我觉得是这样:如果相邻两个点高度相同,那么是过不去的,但是你的代码会一直在两个点之间徘徊。
by crzcqh @ 2023-07-10 09:50:56
@chenyikun2013 谢谢dalao! 所以加个vist可能就行了。