考试的时候写了个dfs找出来了，最后处理的时候想到了贪心，但是正确性没有想通。然后想了想动规，也没想通。最后没办法，用状态的话用了个状压，弄了40分。
正解是bfs+贪心。Dfs也有过的。
下面题解引用自他人：
整体的思路是这样的：
从第一层的每一个点开始往下做一次搜索，每一次搜索可以覆盖到最后一行的一段，我们就可以把它看成是一条线段；
做完搜索之后我们就得到了一坨线段。。然后这就变成了一个线段覆盖问题，用最少的线段来把最后一行盖满，当然也存在无论如何都盖不满的情况。。
下面来说说线段覆盖的思路：
把所有的线段按照左端点排序，之后先以第一条线段为基准，第一条线段能覆盖到的地方就是我们现在能覆盖到的区域（下面成为灰色区域）；然后从左往右开始扫，找一条左端点在灰色区域内，而右端点伸出灰色区域最长的线段，就取这条线端，更新灰色区域，一直找扫完最后一条线段为止，贪心就能求出来最小的线段数；
其实有一个小小的优化：
关于第一行，其实是不必要每一个点做一次搜索的，我们发现只有在这个点的高度>=它左边的点而且又>=它右边的点这种情况下才需要做搜索，因为如果该点的高度比它左右两边任意一个点低的话，做那个点的时候就已经把它给搜索过了，是冗余的，所以没必要；
注意（我犯的错误）：
① 一定要一个点做一次独立的搜索，切忌把所有的一起搜索，那样会T掉。用bfs的话也会内存超限
② 搜索的时候要打标记免得重复，不然也会T掉
证明如果有解线段一定是连续的：
可能会想到有没有拐着弯线段不连续的情况。这种情况其实就是无解的情况。因为如果中间存在空白，说明上面下不来，那么所有的水都下不来。
代码有注解：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define pos2(i,a,b) for(int i=(a);i>=(b);i--)
#define N 510
int n,m;
struct haha
{
int fir;
int hang,lie;
};
struct qian
{
int from,to;
qian(){from=0x7fffffff;}
}cun[N];
int hei[N][N];
int flag[N];
int biao[N][N];
void bfs()
{
pos(i,1,m)
{
if(hei[1][i]>=hei[1][i-1]&&hei[1][i]>=hei[1][i+1])
{
queue<haha> q;
memset(biao,0,sizeof(biao));
haha tmp;
tmp.hang=1;
tmp.lie=i;
tmp.fir=i;
q.push(tmp);
while(!q.empty())
{
haha tmp=q.front();
if(tmp.hang==n)
{
cun[tmp.fir].from=min(cun[tmp.fir].from,tmp.lie);
cun[tmp.fir].to=max(cun[tmp.fir].to,tmp.lie);
flag[tmp.lie]=1;
}
if(tmp.lie-1>0&&hei[tmp.hang][tmp.lie]>hei[tmp.hang][tmp.lie-1]&&biao[tmp.hang][tmp.lie-1]==0)
{
haha tmp2=tmp;
tmp2.lie--;
biao[tmp.hang][tmp.lie-1]=1;
q.push(tmp2);
}
if(tmp.lie+1<=m&&hei[tmp.hang][tmp.lie]>hei[tmp.hang][tmp.lie+1]&&biao[tmp.hang][tmp.lie+1]==0)
{
haha tmp2=tmp;
tmp2.lie++;
biao[tmp.hang][tmp.lie+1]=1;
q.push(tmp2);
}
if(tmp.hang+1<=n&&hei[tmp.hang][tmp.lie]>hei[tmp.hang+1][tmp.lie]&&biao[tmp.hang+1][tmp.lie]==0)
{
haha tmp2=tmp;
tmp2.hang++;
biao[tmp.hang+1][tmp.lie]=1;
q.push(tmp2);
}
if(tmp.hang-1>0&&hei[tmp.hang][tmp.lie]>hei[tmp.hang-1][tmp.lie]&&biao[tmp.hang-1][tmp.lie]==0)
{
haha tmp2=tmp;
tmp2.hang--;
biao[tmp.hang-1][tmp.lie]=1;
q.push(tmp2);
}
q.pop();
}
}
}
}
int ans;
bool aaa(const qian &a,const qian &b)
{
return a.from<b.from;
}
int main()
{
scanf("%d%d",&n,&m);
pos(i,1,n)
pos(j,1,m)
scanf("%d",&hei[i][j]);
bfs();
pos(i,1,m)
{
if(flag[i]==0)
ans++;
}//如果没有覆盖的情况，输出即可
if(ans)
{
printf("0\n%d",ans);
return 0;
}
sort(cun+1,cun+m+1,aaa);//排序左端点
int cnt;
pos(i,1,m)//找出线段的个数
{
if(cun[i].from==0x7fffffff)
{
cnt=i-1;
break;
}
}
int you=1,Ma=0;
while(1)//贪心答案
{
pos(j,1,cnt)
{
if(cun[j].from<=you)
Ma=max(Ma,cun[j].to);//找出左端点已选择区域内右端点最长值
else
break;
}
you=Ma+1;Ma=0;
ans++;
if(you>m)
break;
}
printf("1\n%d",ans);
return 0;
}