eddh4 @ 2019-08-02 13:56:49
打了好久记忆化,结果神奇地30分,更神奇的是输出ans-1后变成了70分,可答案应该就是ans啊
#include<bits/stdc++.h>
using namespace std;
int r,c,a[105][105],m[105][105],ans=-1;
bool ch[105][105];
int back=-1,ex[4]={0,1,0,-1},ey[4]={1,0,-1,0};
void dfs(int x,int y,int k);
int main(){
scanf("%d%d",&r,&c);
memset(a,2147483647,sizeof(a));
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
scanf("%d",&a[i][j]);
}
}
memset(ch,false,sizeof(ch));
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
dfs(i,j,1);
m[i][j]=back;
back=-1;
ch[i][j]=true;
}
}
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
ans=max(ans,m[i][j]);
}
}
printf("%d",ans);
return 0;
}
void dfs(int x,int y,int k){
if(k>back&&a[x+1][y]>=a[x][y]&&a[x][y+1]>=a[x][y]&&a[x-1][y]>=a[x][y]&&a[x][y-1]>=a[x][y]){
back=k;
return;
}
int x1,y1;
for(int i=0;i<4;i++){
x1=x+ex[i];
y1=y+ey[i];
if(a[x1][y1]<a[x][y]){
if(ch[x1][y1]){
k+=m[x1][y1];
if(back<k){
back=k;
}
k-=m[x1][y1];
return;
}
else{
dfs(x1,y1,k+1);
}
}
}
}
by first_fan @ 2019-08-02 14:02:57
dfs的时候貌似没有判断移动后x,y有没有越界?
by eddh4 @ 2019-08-02 14:26:54
但是一开始就加了墙啊