DWT8125 @ 2021-07-29 22:20:26
RT,改得几乎和第一篇题解一样,就是不知道哪里出问题了
#include<cstdio>
#include<algorithm>
using namespace std;
int r,c,a[101][101],s[101][101],ans=1,dx,dy;
const int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int dfs(int x,int y){
if(s[x][y]) return s[x][y];
for(int i=0;i<4;i++){
dx=x+d[i][0]; dy=y+d[i][1];
if(dx>0&&dx<=r&&dy>0&&dy<=c&&a[x][y]>a[dx][dy]){
dfs(dx,dy);
s[x][y]=max(s[x][y],s[dx][dy]+1);
}
}
return s[x][y];
}
int main(){
scanf("%d%d",&r,&c);
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++){
scanf("%d",&a[i][j]);
s[i][j]=1;
}
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
ans=max(ans,dfs(i,j));
printf("%d",ans);
return 0;
}by PPL_ @ 2021-07-29 22:22:48
s 数组的初值不能提前赋吧。
by Rosaya @ 2021-07-29 22:24:23
您那个读入里面的s[i][j]=1不是直接把记忆化给过掉了吗……
by HYdroKomide @ 2021-07-29 22:24:45
@AC_chenpeizhe20 去掉s[i][j]=1;试试
by DWT8125 @ 2021-07-29 22:28:30
@PPL_ @Dаrk_night @Kevin_FOS 谢谢啦!不过改完好像没用啊,样例给我输出了9
#include<cstdio>
#include<algorithm>
using namespace std;
int r,c,a[101][101],s[101][101],ans=1,dx,dy;
const int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int dfs(int x,int y){
if(s[x][y]) return s[x][y];
s[x][y]=1;
for(int i=0;i<4;i++){
dx=x+d[i][0]; dy=y+d[i][1];
if(dx>0&&dx<=r&&dy>0&&dy<=c&&a[x][y]>a[dx][dy]){
dfs(dx,dy);
s[x][y]=max(s[x][y],s[dx][dy]+1);
}
}
return s[x][y];
}
int main(){
scanf("%d%d",&r,&c);
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
ans=max(ans,dfs(i,j));
printf("%d",ans);
return 0;
}by PPL_ @ 2021-07-29 22:41:01
你的dx，dy不能开成全局变量
by PPL_ @ 2021-07-29 22:41:13
@AC_chenpeizhe20
by DWT8125 @ 2021-07-29 22:51:45
@PPL_ 万分感谢！AC了！！！
（我居然忘了还有栈空间这东东）
by wsdyz2010 @ 2021-10-17 09:41:40
...