ZXZ695 @ 2018-06-10 20:13:41
using namespace std; int r,c,ans=0,a[105][105],b[10009][4],asd[105][105],qwe[105][105];//行R //列C int zx[5]={0,1,0,-1,0},zc[5]={0,0,1,0,-1}; void sq(int l,int r) { int i,j,mid; i=l; j=r; mid=b[(i+j)/2][2]; do { while(b[i][2]<mid)i++; while(b[j][2]>mid)j--;
if(i<=j)
{
swap(b[i][2],b[j][2]);
swap(b[i][1],b[j][1]);
swap(b[i][0],b[j][0]);
i++;j--;
}
}
while(i<=j);
if(i<r) sq(i,r);
if(l<j) sq(l,j);}
void dfs(int x,int y,int ti)
{
ans=max(ti,ans);
if(qwe[x][y]>ti)return;
else
qwe[x][y]=max(qwe[x][y],ti);
for(int i=1;i<=4;i++)
{
int xx=x+zx[i],yy=y+zc[i];
if(xx<1||xx>r||yy<1||yy>c)continue;
if(a[xx][yy]>=a[x][y])continue;
ti++;
dfs(xx,yy,ti);
ti--;
}
}
int main()
{
cin>>r>>c;
int top=0;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
cin>>a[i][j];
top++;
b[top][0]=i;
b[top][1]=j;
b[top][2]=a[i][j];
}
sq(1,top);
for(int i=1;i<=top;i++)
{
asd[b[i][0]][b[i][1]]=i;
//cout<<b[i][2]<<" "<<b[i][0]<<" "<<b[i][1]<<endl;
}
for(int i=top;i>=1;i--)
{
if( asd[b[i][0]][b[i][1]] <=ans )continue;
dfs(b[i][0],b[i][1],1);
}
cout<<ans;
return 0;
}
by 张奕涵 @ 2018-06-19 14:04:37
同第二个点RE...
#include<bits/stdc++.h>
using namespace std;
struct rec{
int x,y;
};
int n,m,ans,f[105][105],h,t;
rec q[10005];
int Map[105][105];
int max(int x,int y){
if(x>y)return(x);return(y);
}
void push(int x,int y,int len){
if(x<=0 || y<=0 || x>n || y>m)return;
q[++t].x=x;q[t].y=y;
f[x][y]=max(f[x][y],len);
ans=max(ans,len);
}
void bfs(int x,int y){
if(f[x][y]>0)return;
h=0;t=0;int xx,yyy,fff;
push(x,y,1);
while(h<=t){
xx=q[++h].x;yyy=q[h].y;fff=f[xx][yyy]+1;
if(Map[xx+1][yyy]<Map[xx][yyy])push(xx+1,yyy,fff);
if(Map[xx-1][yyy]<Map[xx][yyy])push(xx-1,yyy,fff);
if(Map[xx][yyy+1]<Map[xx][yyy])push(xx,yyy+1,fff);
if(Map[xx][yyy-1]<Map[xx][yyy])push(xx,yyy-1,fff);
}
return;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&Map[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
bfs(i,j);
printf("%d",ans);
}