[vijos1777]——引水入城

原题
先bfs，注意一个储水厂可到达的沙漠地区肯定是连续的，之后做区间覆盖就好了

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int maxn=505;
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};
int n,m,h[maxn][maxn],ans;
bool vis[maxn],vist[maxn][maxn];
struct node{
    int l,r;
}e[maxn];
struct odd{
    int x,y;
};
queue <odd> q;
bool cmp(const node &a,const node &b){
    if(a.l<b.l)return 1;
    else if(a.l==b.l)return a.r<b.r;
    return 0;
}
void bfs(int x){
    memset(vist,0,sizeof vist);
    odd st;
    st.x=1;st.y=x;
    q.push(st);vist[1][x]=1;
    while(!q.empty()){
        odd u=q.front();q.pop();
        if(u.x==n){
            vis[u.y]=1;
            if(e[x].r<u.y)e[x].r=u.y;
            if(!e[x].l)e[x].l=u.y,e[x].r=u.y;
            else if(e[x].l>u.y)e[x].l=u.y;
        }
        for(register int i=0;i<4;++i){
            int nx=u.x+dx[i];
            int ny=u.y+dy[i];
            if(nx<1||nx>n||ny<1||ny>m||h[nx][ny]>=h[u.x][u.y]||vist[nx][ny])continue;
            odd neww;
            neww.x=nx,neww.y=ny;q.push(neww);vist[nx][ny]=1;
        }
    }
}
int main(){
    scanf(
    for(register int i=1;i<=n;++i){
        for(register int j=1;j<=m;++j){
            scanf(
        }
    }
    for(register int i=1;i<=m;++i){
        bfs(i);
    }
    bool flag=0;int ct=0;
    for(register int i=1;i<=m;++i){
        if(!vis[i])++ct,flag=1;
    }
    if(flag){
        printf("0\
        return 0;
    }
    sort(e+1,e+m+1,cmp);
    int idx=1,s=1,t,cnt=0;
    while(s<=m){
        t=s;
        for(register int i=idx;i<=m;++i){
            if(e[i].l<=t){
                if(e[i].r>=t)s=e[i].r;
            }
            else {
                idx=i;break;
            }
        }
        cnt++;s++;
    }
    printf("1\
    return 0;
}