引水入城

题目大意
有一个N*M的城市，可以在第一行建蓄水池，水可以往低处流。求能否覆盖最后一行。

若能覆盖，求最小蓄水池数；若不能，求有几个不能覆盖

算法
DFS，求第一行每个点可以覆盖的最下面一行的左右端点，然后做线段覆盖。

代码

#include <cstdio>
#include <memory.h>
#define INF 1<<30
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
const int dx[4]={0,1,0,-1};
const int dy[4]={-1,0,1,0};
int h[1000][1000]={0};
int n,m,cnt=0;;
int l[1000][1000],r[1000][1000];
bool vis[1000][1000]={false};
void dfs(int x,int y){
    cnt++;
    vis[x][y]=true;
    for(int i=0;i<4;i++){
        int xx=x+dx[i],yy=y+dy[i];
        // for(int i=1;i<=cnt;i++)
            // printf("    ");
        // printf("%d %d %d %d\n",x,y,xx,yy);
        if(xx<1 || yy<1 || xx>n || yy>m)
            continue;
        if(h[xx][yy]>=h[x][y])
            continue;
        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]);
    }
    cnt--;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&h[i][j]);
    memset(l,0x3f3f,sizeof(l));
    memset(r,0,sizeof(r));
    for(int i=1;i<=m;i++)
        l[n][i]=r[n][i]=i;
    for(int i=1;i<=m;i++)
        if(!vis[1][i])
            dfs(1,i);
    bool f=false;
    int c=0;
    for(int i=1;i<=m;i++)
        if(!vis[n][i]){
            f=true;
            c++;
        }
    if(f){
        printf("0\n%d\n",c);
        return 0;
    }
    int le=1;
    c=0;
    // for(int i=1;i<=n;i++){
        // for(int j=1;j<=m;j++)
            // printf("%d ",l[i][j]);
        // printf("\n");
    // }
    // for(int i=1;i<=n;i++){
        // for(int j=1;j<=m;j++)
            // printf("%d ",r[i][j]);
        // printf("\n");
    // }
    while(le<=m){
        int ri=0;
        for(int i=1;i<=m;i++)
            if(l[1][i]<=le)
                ri=max(ri,r[1][i]);
        c++;
        le=ri+1;
    }
    printf("1\n%d",c);
    return 0;
}