一道非常好的搜索题！
题目要求一个城市能修建水利工程，必须在一个比他海拔高而且修建了水利工程的城市旁边，那我们可以从每个水库旁边的点开始进行BFS，判断最后一行有哪些点能到达，从而判断可行性。这个做法很简单粗暴，只要一开始把沿着水库边上所有点全都压到队列里面，直接BFS即可，时间复杂度不超过O（nm）。
可行性很好判断，关键在于如何计算出最少需要多少个水库。仔细想一想之后发现，一个水库能供给到的靠沙漠的城市，它必然是一段连续的区间，否则我们必然有方法使得区间联通（只可能是中间高，只要从中间流就行了。）那我们其实是可以转化成线段覆盖，只要求出每个点能流到的区间是多少就好了。
又一个暴力方法出来了……从每个点开始BFS能流到的区间。但是这样的复杂度太大了，O（m^2*n），很可能超时。
再想一想，我们要求的是一个点它能流到的区间的左右端点。我们其实完全可以用已经搜索过的结果去更新答案，而没有必要每次都重新搜索一遍。所以解决问题的方法出现了，记忆化搜索！只要在dfs的时候，记录一下每个点被更新的最远的值是多少，遇到已经走过的格子，不搜索直接返回即可。最后做一次线段覆盖，直接枚举即可。注意在初始化能拓展的最左边的端点的时候要预处理为极大值。
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 505; const int INF = 1000000009; const ll mod = 1e9+7; ll read() { ll ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } int l[M][M],r[M][M],h[M][M],n,m,dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1},cnt,g = 1; bool vis[M][M],flag; void dfs(int x,int y) { vis[x][y] = 1; rep(i,0,3) { int kx = x + dx[i],ky = y + dy[i]; if(kx < 1 || kx > n || ky < 1 || ky > m) continue; if(h[kx][ky] >= h[x][y]) continue; if(!vis[kx][ky]) dfs(kx,ky); l[x][y] = min(l[x][y],l[kx][ky]),r[x][y] = max(r[x][y],r[kx][ky]); } } int main() { n = read(),m = read(); memset(l,0x3f,sizeof(l)); rep(i,1,m) l[n][i] = r[n][i] = i; rep(i,1,n) rep(j,1,m) h[i][j] = read(); rep(i,1,m) if(!vis[1][i]) dfs(1,i); rep(i,1,m) if(!vis[n][i]) cnt++,flag = 1; if(flag) printf("0 %d ",cnt),exit(0); while(g <= m) { int cur = 0; rep(i,1,m) if(l[1][i] <= g) cur = max(cur,r[1][i]); cnt++,g = cur + 1; } printf("1 %d ",cnt); return 0; }