题目链接：https://www.luogu.com.cn/problem/P1514
题意大致是：给定一个（n,m）的数值矩阵，可以在第一行建造水库，如果一个格子周围的某格子值小于它，那水就可以流到它周围的那个格子，问需要在第一行建造多少水库使得最后一行能够被完全覆盖，如果不能完全覆盖就求出不能覆盖的格子的数量。
主要思路就是在第一行每个点出发的水能到达第n行的区间可以获得（可以用反证法证明每个点出发的水如果能到达第n行那么它的覆盖区间一定是连续的），如果能够完全覆盖第n行则用最小区间数覆盖可以求出最少需要多少个点可以覆盖第n行，
代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
#define pf printf
#define mem(a,b) memset(a,b,sizeof(a))
#define prime1 1e9+7
#define prime2 1e9+9
#define scand(x) scanf("%llf",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define scan(a) scanf("%d",&a)
#define dbg(args) cout<<#args<<":"<<args<<endl;
#define pb(i) push_back(i)
#define ppb(x) pop_back(x)
#define inf 0x3f3f3f3f
#define maxn 1005
int n,m,t,a[maxn][maxn],l[maxn][maxn],r[maxn][maxn],vis[maxn][maxn];
//l[i][j]从(i,j)位置出发的水最多能覆盖到最后一行的左端的位置,
//r[i][j]从(i,j)位置出发的水最多能覆盖到最后一行的最右端的位置
int dir[][]={{,},{,-},{-,},{,}};
void dfs(int x,int y)
{
vis[x][y]=true;//表明(x,y)位置的l，r信息都被处理过
int xx,yy;
f(i,,)
{
xx=x+dir[i][];
yy=y+dir[i][];
if(xx<=||xx>n||yy<=||yy>m)continue;
if(a[xx][yy]>=a[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]);
}
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
std::ios::sync_with_stdio(false);
scan(n);
scan(m);
f(i,,n)
f(j,,m)
{
scan(a[i][j]);
}
mem(l,inf);
mem(r,-inf);
f(,,m)
{
l[n][i]=r[n][i]=i;//最下面一层，初始情况区间只覆盖自己
}
f(i,,m)
{
if(!vis[][i])
dfs(,i);
}
bool flag=true;
int cnt=;
f(i,,m)
{
if(!vis[n][i])
{
flag=false;
cnt++;
}
}
if(!flag)
{
pf("0\n%d",cnt);//有多少个点无法覆盖
}
else
{
int num=;
int left=,maxr=;//最小区间数覆盖
while(left<=m)
{
maxr=;
f(i,,m)
{
if(l[][i]<=left)//找到覆盖left点的区间右端值的最大值
maxr=max(maxr,r[][i]);
}
left=maxr+;
num++;
}
pf("1\n%d\n",num);
/* f(i,1,m)
{
pf("%d %d\n",l[1][i],r[1][i]);
}*/
}
return ;
}