题目链接：https://vijos.org/p/1777

思路：网上的大神思路写的很清晰了，每个水站覆盖的干旱城市在有解情况下一定是一个区间，否则无解，然后剩下的就是线段覆盖问题啦。

求每个水站覆盖的区间：

用记忆化搜索，设l(i,j),r(i,j)分别表示从(i,j)可以到达的区间左端点和右端点，那么每次Flood fill时遇到已到达的位置就可以直接使用信息，不需要再次进行搜索，这样就将Flood fill的复杂度降到O(nm)。（记忆化使用深搜的话更加方便，实在不行就手写栈吧。。（没开O2的STL实在好慢。。。））

线段覆盖：实在不清楚DP的写法，所以我自己写了一个O(n log n)的贪心，现将线段按照左端点排序，然后设一个数组f(),初始时全为正无穷（除0）,f(0)=0,然后扫描线段，每次取区间[l-1,m]中的最小值，设为Fmin,然后更新f(r)为min(f(r),Fmin+1),全部扫描完毕后f(m)即为答案。（用树状数组或线段树优化可以做到O(n log n)，建议常数较小的BIT）

复杂度：flood fill O(nm) 线段覆盖O(m log m) 所以总复杂度O(nm+m log m)

速度勉勉强强(vijos)：

a1ec08fa513d269786796c4d57fbb2fb4316d87c.jpg.png

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 510
#define lowbit(x)(((~(x))+1)&x)
#define inf 0x7fffffff
#define update(v) l[X[v]][Y[v]]=min(l[X[v]][Y[v]],l[X[v+1]][Y[v+1]]),r[X[v]][Y[v]]=max(r[X[v]][Y[v]],r[X[v+1]][Y[v+1]]);
 
bool f[MAXN][MAXN];
int n,m,h[MAXN][MAXN],ansv=0,ansm=0,l[MAXN][MAXN],r[MAXN][MAXN],X[MAXN*MAXN],Y[MAXN*MAXN],T[MAXN];
struct node{
        int x,y;
        node (int _x,int _y):x(_x),y(_y){
        }
};
queue<node>Q;
struct saver{
        int l,r;
} Seg[MAXN];
int Sn=0;
bool Cmp(saver x,saver y){return x.l<y.l;}
void dfs(int v){
        l[X[v]][Y[v]]=inf,r[X[v]][Y[v]]=-inf,f[X[v]][Y[v]]=false;
        if(X[v]==n) l[X[v]][Y[v]]=r[X[v]][Y[v]]=Y[v];
        if(X[v]-1&&h[X[v]-1][Y[v]]<h[X[v]][Y[v]]){
             X[v+1]=X[v]-1,Y[v+1]=Y[v];
               if(f[X[v]-1][Y[v]]) dfs(v+1);
               update(v);
        }
        if(X[v]+1<=n&&h[X[v]+1][Y[v]]<h[X[v]][Y[v]]){
                   X[v+1]=X[v]+1,Y[v+1]=Y[v];
               if(f[X[v]+1][Y[v]]) dfs(v+1);
               update(v);
        }
        if(Y[v]-1&&h[X[v]][Y[v]-1]<h[X[v]][Y[v]]){
             X[v+1]=X[v],Y[v+1]=Y[v]-1;
               if(f[X[v]][Y[v]-1]) dfs(v+1);
               update(v);
        }
        if(Y[v]+1<=m&&h[X[v]][Y[v]+1]<h[X[v]][Y[v]]){
             X[v+1]=X[v],Y[v+1]=Y[v]+1;
               if(f[X[v]][Y[v]+1]) dfs(v+1);
               update(v);
        }
}
int Min(int x){int rec=inf;for(int i=x;i;i-=lowbit(i)) rec=min(rec,T[i]);return rec;}
void Add(int x,int y){for(int i=x;i<=m+1;i+=lowbit(i)) T[i]=min(T[i],y);}
void getint(int&x){scanf("%d",&x);}
int main(){
        getint(n),getint(m);
        for(int i=0;i++<n;)for(int j=0;j++<m;)getint(h[i][j]);
        memset(f,true,sizeof(f));
        for(int i=0;i++<m;){
               while(!Q.empty()) Q.pop();
               Q.push(node(1,i));
               while(!Q.empty()){
                       node u=Q.front();
                       Q.pop();
                       if(!f[u.x][u.y])continue;
                       f[u.x][u.y]=false;
                       if(u.x-1&&h[u.x-1][u.y]<h[u.x][u.y]) Q.push(node(u.x-1,u.y));
                       if(u.x+1<=n&&h[u.x+1][u.y]<h[u.x][u.y]) Q.push(node(u.x+1,u.y));
                       if(u.y-1&&h[u.x][u.y-1]<h[u.x][u.y]) Q.push(node(u.x,u.y-1));
                       if(u.y+1<=m&&h[u.x][u.y+1]<h[u.x][u.y]) Q.push(node(u.x,u.y+1));
               }
        }
        for(int i=0;i++<m;)if(f[n][i]) ansv++;
        if(ansv){
               printf("0\n%d\n",ansv);
               return 0;
        }
        memset(f,true,sizeof(f));
        for(int i=0;i++<m;){
               X[1]=1,Y[1]=i;
               dfs(1);
               if(l[1][i]<inf&&r[1][i]>-inf){
                       Seg[Sn].l=l[1][i],Seg[Sn].r=r[1][i];
                       Sn++;
               }
        }
        for(int i=0;i++<m;) T[i]=inf;
        T[m+1]=0;
        sort(Seg,Seg+Sn,Cmp);
        for(int i=0;i<Sn;i++){
               Add(m-Seg[i].r+1,Min(m-Seg[i].l+2)+1);
        }
        printf("1\n%d\n",T[1]);
        return 0;
}