记录编号	585510	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.047 s
提交时间	2023-12-14 21:10:42	内存使用	1.40 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
const int N = 510;
int n,m;
int a[N][N],f[N];
bool v[N][N];
struct made{
    int x,y;
}e[N];
void sou(int x,int y){
    if(v[x][y])return;
    v[x][y] = 1;
    if(x > 1 && a[x-1][y] < a[x][y])sou(x-1,y);
    if(x < n && a[x+1][y] < a[x][y])sou(x+1,y);
    if(y > 1 && a[x][y-1] < a[x][y])sou(x,y-1);
    if(y < m && a[x][y+1] < a[x][y])sou(x,y+1);
}
void dfs(int x,int y,int f,int l){
    if(v[x][y])return;
    if(x == 1){
        if(f == 1)e[y].x = l;
        if(f == 0)e[y].y = l;
    }
    v[x][y] = 1;
    if(x > 1 && a[x-1][y] > a[x][y])dfs(x-1,y,f,l);
    if(x < n && a[x+1][y] > a[x][y])dfs(x+1,y,f,l);
    if(y > 1 && a[x][y-1] > a[x][y])dfs(x,y-1,f,l);
    if(y < m && a[x][y+1] > a[x][y])dfs(x,y+1,f,l);
}
bool check(){
    for(int i = 1;i <= m;i++)
        if(v[n][i] == 0)return 1;
    return 0;
}
int main(){
    freopen("flow.in","r",stdin);
    freopen("flow.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)scanf("%d",&a[i][j]);
    for(int i = 1;i <= m;i++)sou(1,i);
    if(check()){
        printf("0\n");
        int ans = 0;
        for(int i = 1;i <= m;i++)
            if(v[n][i] == 0)ans++;
        printf("%d\n",ans);
        return 0;
    }
    memset(v,0,sizeof(v));
    for(int i = 1;i <= m;i++)dfs(n,i,1,i);
    memset(v,0,sizeof(v));
    for(int i = m;i >= 1;i--)dfs(n,i,0,i);
    memset(f,0x3f,sizeof(f));
    f[0] = 0;
    for(int i = 1;i <= m;i++)
        for(int j = 1;j <= m;j++)
            if(i >= e[j].x && i <= e[j].y)f[i] = min(f[i],f[e[j].x-1]+1);
    printf("1\n%d\n",f[m]);
    
    
    return 0;
    
}