引水入城

#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分，超大的数据会超时