#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<fstream>
using namespace std;
struct rec{
int a,b;
};
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
int map[521][521],g[521][521];
int l[521],r[521],a[521],f[521];
int n,m,pd;
queue<rec> team;
int main(){
freopen("flow.in","r",stdin);
freopen("flow.out","w",stdout);
cin>>n>>m;
memset(r,0,sizeof(r));
memset(a,0,sizeof(a));
for(int i=1;i<=m;i++) l[i]=2147483647;
for(int i=1;i<=m;i++) f[i]=555;
f[0]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&map[i][j]);
pd=0;
for(int i=1;i<=m;i++){
memset(g,0,sizeof(g));
rec now;
now.a=1;
now.b=i;
g[1][i]=1;
team.push(now);
while(not team.empty()){
rec now=team.front();
for(int j=0;j<=3;j++){
int nowx=now.a+dx[j];
int nowy=now.b+dy[j];
if(nowx<1||nowx>n||nowy<1||nowy>m) continue;
if(g[nowx][nowy]==1) continue;
if(map[now.a][now.b]<=map[nowx][nowy]) continue;
rec nowp;
nowp.a=nowx;
nowp.b=nowy;
g[nowx][nowy]=1;
team.push(nowp);
if(nowx==n){
l[i]=min(l[i],nowy);
r[i]=max(r[i],nowy);
if(a[nowy]==0){
a[nowy]=1;
pd++;
}
}
}
team.pop();
}
}
if(pd==m){
for(int i=1;i<=m;i++)
for(int j=l[i];j<=r[i];j++)
f[j]=min(f[j],f[l[i]-1]+1);
cout<<1<<endl<<f[m]<<endl;
}
else
cout<<0<<endl<<m-pd<<endl;
return 0;
}//90分,超大的数据会超时
引水入城
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...