亚由亚由 @ 2019-07-22 16:56:01
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m,cnt,h[100005],an,d[100005],s[100005],jl[105][105],v[100005],k[100005];
struct ll
{
int nx;
int to;
}a[100005];
void ad(int x,int y)
{
k[y]++;
a[++cnt].nx=h[x];
a[cnt].to=y;
h[x]=cnt;
}
int sp(int v0)
{
int i,j,p;
queue<int> q;
q.push(v0);
for(i=1;i<=n*m;i++)
{
d[i]=-0x3f3f3f3f;
v[i]=0;
}
v[v0]=1;
d[v0]=0;
while(!q.empty())
{
i=q.front();
q.pop();
v[i]=0;
for(j=h[i];j;j=a[j].nx)
{
p=a[j].to;
if(d[p]<d[i]+1)
{
d[p]=d[i]+1;
an=max(an,d[p]);
if(v[p]==0)
{
q.push(p);
v[p]=1;
}
}
}
}
}
int main()
{
int i,j,x,y;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&jl[i][j]);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(i!=1&&jl[i-1][j]>jl[i][j])
ad((i-1)*m+j,(i-2)*m+j);
if(i!=n&&jl[i+1][j]>jl[i][j])
ad((i-1)*m+j,i*m+j);
if(j!=1&&jl[i][j-1]>jl[i][j])
ad((i-1)*m+j,(i-1)*m+j-1);
if(j!=n&&jl[i][j+1]>jl[i][j])
ad((i-1)*m+j,(i-1)*m+j+1);
}
for(i=1;i<=n*m;i++)
if(!k[i])
sp(i);
printf("%d\n",an+1);
return 0;
}by 亚由亚由 @ 2019-07-22 17:03:32
是不是spfa被卡了
by Lily_White @ 2019-07-22 17:19:55
#2==#10
by 没有输入 @ 2019-07-26 21:15:13
维护一个最小高度，两个剪枝：
这样#2 896ms
#include<bits/stdc++.h>
using namespace std;
int r,c,a[105][105],Min=1e9,ans=1,dx[4]= {0,0,-1,1},dy[4]= {-1,1,0,0};
void dfs(int x,int y,int sum)
{
if(a[x][y]-Min+sum+1<=ans) return;
if((a[x+1][y]>=a[x][y]||x>=r)&&(a[x-1][y]>=a[x][y]||x<2)&&(a[x][y+1]>=a[x][y]||y>=c)&&(a[x][y-1]>=a[x][y]||y<2))
{
ans=max(ans,sum);
return;
}
for(int i=0;i<4;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>0&&ny>0&&nx<=r&&ny<=c&&a[nx][ny]<a[x][y]) dfs(nx,ny,sum+1);
}
}
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]),Min=min(Min,a[i][j]);
for(int i=1; i<=r; i++)
for(int j=1; j<=c; j++)
if(a[i][j]-Min+1>ans) dfs(i,j,1);
printf("%d",ans);
return 0;
}