记录编号	605013	评测结果	AAAAAAAAAA
题目名称	521.[NOIP 2010]引水入城	最终得分	100
用户昵称	Ruyi	是否通过	通过
代码语言	C++	运行时间	0.268 s
提交时间	2025-08-13 13:46:42	内存使用	6.11 MiB

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,a[501][501],l[501][501],r[501][501],d[4][2]={{0,1},{1,0},{-1,0},{0,-1}},vis[501][501];
bool flag=false;
void dfs(int x,int y){
    vis[x][y]=1;
    for(int i=0;i<4;i++){
        int xx=x+d[i][0],yy=y+d[i][1];
        if(xx>0&&xx<=n&&yy>0&&yy<=m&&a[x][y]>a[xx][yy]){
            if(!vis[xx][yy]) dfs(xx,yy);
            l[x][y]=min(l[x][y],l[xx][yy]);
            r[x][y]=max(r[x][y],r[xx][yy]);
        }
    }
    return ;
}
int main(){
    freopen("flow.in","r",stdin);
    freopen("flow.out","w",stdout);
    cin>>n>>m;
    memset(l,0x3f,sizeof(l));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        cin>>a[i][j];
        if(i==n) l[i][j]=r[i][j]=j;
    }
    for(int i=1;i<=m;i++)
    if(!vis[1][i]) dfs(1,i);
    for(int i=1;i<=m;i++)
    if(!vis[n][i]){
        flag=true;
        ans++;
    }
    if(flag){
        cout<<0<<endl<<ans<<endl;
        return 0;
    }
    int c1=1,c2=r[1][1];
    while(c1<=m){
        for(int i=1;i<=m;i++)
        if(l[1][i]<=c1) c2=max(c2,r[1][i]);
        c1=c2+1;
        ans++;
    }
    cout<<1<<endl<<ans<<endl;
    return 0;
}