记录编号	585541	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.167 s
提交时间	2023-12-15 21:40:43	内存使用	3.21 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int disx[5]={0,-1,1,0,0};
int disy[5]={0,0,0,-1,1};
int n,m,a[510][510],b[510][510],b2[510],l[510][510],r[510][510],d[510],f[510][510],ans=0;
int p(int x,int y)
{
    if(x>=1&&x<=n&&y>=1&&y<=m)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
void dfs(int x,int y)
{
    b[x][y]=1;
    for(int i=1;i<=4;i++)
    {
        int dx=x+disx[i];
        int dy=y+disy[i];
        if(a[dx][dy]<a[x][y]&&p(dx,dy)==1)
        {
            if(b[dx][dy]==0)
            {
               dfs(dx,dy); 
            }
            l[x][y]=min(l[x][y],l[dx][dy]);
            r[x][y]=max(r[x][y],r[dx][dy]);
        }
    }
}
int main()
{
    freopen("flow.in","r",stdin);
	freopen("flow.out","w",stdout);
    memset(l,0x3f,sizeof(l));
    memset(r,0,sizeof(r));
    memset(b2,0,sizeof(b2));
    memset(f,0x3f,sizeof(f));
    memset(d,0x3f,sizeof(d));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=m;i++)
    {
        l[n][i]=i;
        r[n][i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        if(a[1][i-1]<=a[1][i]&&a[1][i+1]<=a[1][i]&&b[1][i]==0)
        {
            dfs(1,i); 
        }
    }
    int sum=0;
    for(int i=1;i<=m;i++)
    {
        if(b[n][i]==0)
        {
            sum++;
        }
    } 
    if(sum!=0)
    {
        cout<<'0'<<endl;
        cout<<sum;
        return 0;
    }
    cout<<'1'<<endl;
    int x=1,y=r[1][1];
    while(x<=m)
    {
        for(int i=1;i<=m;i++)
        {
            if(l[1][i]<=x)
            {
                y=max(y,r[1][i]);
            }
        }
        x=y+1;
        ans++;
    }
    cout<<ans; 
    return 0;
}