没看题解,思路如下:
易知从大到小和从小到大是一个东西,因此
维护原数组a,顺序数组s,求解数组l
各个点从小到大排一遍序
从小到大去搜索每一个点,看能否向旁边更大的点扩充并使它的道路长度更大
请问是我的思路错了还是代码的某些细节出现了问题(样例已过得分60pts)
code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=110,tx[4]={0,0,-1,1},ty[4]={-1,1,0,0};
int a[maxn][maxn],l[maxn][maxn];
struct node{int v,x,y;}s[maxn*maxn];
bool cmp(node x,node y){return x.v<y.v;}
int main(){
memset(l,0,sizeof(l));memset(s,0,sizeof(s));
int m,n;scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);l[i][j]++;
s[i*n+j-n].v=a[i][j],s[i*n+j-n].x=i,s[i*n+j-n].y=j;
}
}
sort(s+1,s+m*n+1,cmp);
for(int i=1;i<=n*m;i++){
int v=s[i].v,x=s[i].x,y=s[i].y;
for(int i=0;i<=3;i++){
int vx=x+tx[i],vy=y+ty[i];
if(vx<1||vx>m||vy<1||vy>n) continue;
if(a[vx][vy]>v) l[vx][vy]=max(l[vx][vy],l[x][y]+1);
}
// for(int i=1;i<=m;i++){
// for(int j=1;j<=n;j++){
// printf("%d ",l[i][j]);
// }
// printf("\n");
// }
// printf("\n");
}
// for(int i=1;i<=m*n;i++)
// printf("%d:%d %d %d\n",i,s[i].x,s[i].y,s[i].v);
printf("%d\n",l[s[m*n].x][s[m*n].y]);
return 0;
}