这道题开始看好像并没有什么思路，和搜索好像也并没有什么关系。但是我们手玩下样例就会发现，思路其实就三句话：（写这道题的时候在代码里写的）
//我们想知道从第1行的每列往下到干旱区的范围
//要求这个直接bfs就行了
//然后就转换为了一个最小线段覆盖了
写了个bfs，在学长的blog那里看了看线段覆盖怎么搞，于是就交了，开始是30分，因为bfs的时候我只用了3个方向。开始以为它是不能向上建水站的，后来想想其实也可以，只要满足有公共边+高度有落差就行了...再交就90分了$qwq$，T了一个点，开了氧气优化+快读，然后A了（？？？）
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n,m,ans,tot;
int la[600][600],tong[600],fla[600];
bool vis[600][600];
int dx[5]={0,0,1,0,-1};
int dy[5]={0,-1,0,1,0};
struct segment{
int l,r;
}p[600];
void re(int &x)
{
x=0;
char ch=getchar();
bool flag=false;
while(ch<'0'||ch>'9') flag|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
x=flag ? -x : x;
}
bool valid(int x,int y)
{
if(x>=1&&x<=n&&y>=1&&y<=m) return 1;
return 0;
}
bool cmp(segment x,segment y)
{
return x.l<y.l;
}
void bfs(int x,int y)
{
memset(vis,0,sizeof(vis));
queue<pair<int,int> >q;
q.push(make_pair(x,y));
vis[x][y]=1;
while(!q.empty())
{
int nx=q.front().first;
int ny=q.front().second;
q.pop();
for(int i=1;i<=4;i++)
{
int xx=nx+dx[i];
int yy=ny+dy[i];
if(valid(xx,yy)&&la[nx][ny]>la[xx][yy]&&!vis[xx][yy])
q.push(make_pair(xx,yy)),vis[xx][yy]=1;
}
}
int l=99999,r=0;
for(int j=1;j<=m;j++)
if(vis[n][j]) tong[y]++,fla[j]++,l=min(l,j),r=max(r,j);
if(!tong[y]) return ;
p[++tot].l=l,p[tot].r=r;
}
int main()
{
//我们想知道从第1行的每列往下到干旱区的范围
//要求这个直接bfs就行了
//然后就转换为了一个最小线段覆盖了
re(n);re(m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
re(la[i][j]);
for(int j=1;j<=m;j++)
bfs(1,j);
// for(int j=1;j<=m;j++) printf("%d %d
",p[j].l,p[j].r);
for(int j=1;j<=m;j++)
if(!fla[j]) ans++;
if(ans) {printf("0
%d",ans);return 0;}
sort(p+1,p+tot+1,cmp);
int s=1;
for (int i=1;i<=m;i++)
{
int r=0;
for (int j=1;j<=m;j++)
if (p[j].l<=s&&p[j].r>=s) r=max(r,p[j].r);
ans++;
s=r+1;
if (s>m) break;
}
printf("1
%d",ans);
return 0;
}
为什么会T呢？刚才我们的算法复杂度其实严格是$O(n3+nlogn+n2)$的。开始不解为什么搜索会是$O(n3)$，想了想后发现这是网格图，遍历所有点一遍是$O(n2)$的。而本题极限数据$500$，可能会跑到一亿，超时。
刚才我们有最直观的想法：从第一行的每列出发向下搜索，但事实上我们可以不对所有第一行的位置进行向下搜索。只对那些满足$h[1][i]>=h[1][i-1]$而且$h[1][i]>=h[1][i+1]$的点进行搜索。因为当前点如果不满足这些条件，那么它形成的区间一定可以被其他区间覆盖，这个区间就没什么用了。
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n,m,ans,tot;
int la[600][600],tong[600],fla[600];
bool vis[600][600];
int dx[5]={0,0,1,0,-1};
int dy[5]={0,-1,0,1,0};
struct segment{
int l,r;
}p[600];
void re(int &x)
{
x=0;
char ch=getchar();
bool flag=false;
while(ch<'0'||ch>'9') flag|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
x=flag ? -x : x;
}
bool valid(int x,int y)
{
if(x>=1&&x<=n&&y>=1&&y<=m) return 1;
return 0;
}
bool cmp(segment x,segment y)
{
return x.l<y.l;
}
void bfs(int x,int y)
{
memset(vis,0,sizeof(vis));
queue<pair<int,int> >q;
q.push(make_pair(x,y));
vis[x][y]=1;
while(!q.empty())
{
int nx=q.front().first;
int ny=q.front().second;
q.pop();
for(int i=1;i<=4;i++)
{
int xx=nx+dx[i];
int yy=ny+dy[i];
if(valid(xx,yy)&&la[nx][ny]>la[xx][yy]&&!vis[xx][yy])
q.push(make_pair(xx,yy)),vis[xx][yy]=1;
}
}
int l=99999,r=0;
for(int j=1;j<=m;j++)
if(vis[n][j]) tong[y]++,fla[j]++,l=min(l,j),r=max(r,j);
if(!tong[y]) return ;
p[++tot].l=l,p[tot].r=r;
}
int main()
{
//我们想知道从第1行的每列往下到干旱区的范围
//要求这个直接bfs就行了
//然后就转换为了一个最小线段覆盖了
re(n);re(m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
re(la[i][j]);
for(int j=1;j<=m;j++)
if(la[1][j]>=la[1][j-1]&&la[1][j]>=la[1][j+1])
bfs(1,j);
// for(int j=1;j<=m;j++) printf("%d %d
",p[j].l,p[j].r);
for(int j=1;j<=m;j++)
if(!fla[j]) ans++;
if(ans) {printf("0
%d",ans);return 0;}
sort(p+1,p+tot+1,cmp);
int s=1;
for (int i=1;i<=m;i++)
{
int r=0;
for (int j=1;j<=m;j++)
if (p[j].l<=s&&p[j].r>=s) r=max(r,p[j].r);
ans++;
s=r+1;
if (s>m) break;
}
printf("1
%d",ans);
return 0;
}