https://www.luogu.org/problem/show?pid=1514
先用dfs搜索，从最上面的一行往下拓展，所有点拓展完后，扫描最后一行是否有没被染上色的，有则说明 不能满足要求； 如果没有，在用dfs，计算出最上面一行的每个点（大于等于两边的点）能拓展到的最左端和最右端，然后就转化成了区间覆盖问题。
区间覆盖问题是给你几个区间，然后给你一个大区间，用尽量少的小区间来覆盖大区间。 区间覆盖问题的解法有两种，我只会贪心做法： 我们把各个区间按照 L 升序排序，然后每次找 l 小于等于当前 L 中 r 最大的。然后将L更新为找出的最大的r, 一直到L到达终点。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; int n,m,a[509][509],color,cnt; struct H{ int l,r; }st[509]; bool f[509][509]; int dx[]={0,0,0,1,-1},dy[]={0,1,-1,0,0}; int L,R; bool cmp(H x,H y) { if(x.l==y.l) return x.r>y.r; return x.l<y.l; } void dfs(int x,int y) { if(x==n) { st[cnt].l=min(st[cnt].l,y); st[cnt].r=max(st[cnt].r,y); } int flag=0; for(int i=1;i<=4;i++) { if(x+dx[i]>=1&&x+dx[i]<=n&&y+dy[i]>=1&&y+dy[i]<=m) if(a[x][y]>a[x+dx[i]][y+dy[i]]&&f[x+dx[i]][y+dy[i]]==0) { flag=1; f[x+dx[i]][y+dy[i]]=color; dfs(x+dx[i],y+dy[i]); } } //if(!flag) return; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); for(int i=1;i<=m;i++) if(a[1][i]>=a[1][i-1]&&a[1][i]>=a[1][i+1]){ f[1][i]=++color; dfs(1,i); } int z=0; for(int i=1;i<=m;i++) if(!f[n][i]) z++; if(z){printf("0\n%d",z);return 0;} color=1; for(int i=1;i<=m;i++) if(a[1][i]>=a[1][i-1]&&a[1][i]>=a[1][i+1]) { cnt++; memset(f,0,sizeof(f)); st[cnt].l=m+1,st[cnt].r=0; dfs(1,i); } sort(st+1,st+cnt+1,cmp); L=0;int ans=0; while(L<m) { int maxn=0; for(int i=1;i<=cnt;i++) { if(st[i].l<=L+1) maxn=max(maxn,st[i].r); } L=maxn; ans++; } printf("1\n%d",ans); return 0; }