疯狂爆搜233333 dfsdfs%%%% 许多大佬都用bfs判断，这里我用了dfs，就不用再写bfs了。 思路 很容易发现区间一定是连续的，否则不行，就可以先爆搜出区间左和右，转化为一个区间覆盖问题
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int n,m,ans; struct st{ int l,r; }s[1999]; int cmp(const st &a,const st &b) { if(a.l<b.l||a.l==b.r&&a.r<b.r)return 1; return 0; } int a[1999][1999],f[1999][1999],q[1999][1999],ff[19999]; int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1},maxn=0; int dfs(int w,int x,int y) { if(x==n) { s[w].l=min(s[w].l,y);s[w].r=max(s[w].r,y); } for(int i=0;i<=2;i++) { int xxx=x+xx[i]; int yyy=y+yy[i]; if(xxx<1||xxx>n||yyy<1||yyy>m) continue; if(a[xxx][yyy]<a[x][y]&&!q[xxx][yyy]) { q[xxx][yyy]=1; dfs(w,xxx,yyy); } } } 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]) { q[1][i]=1; dfs(i,1,i); } for(int i=1;i<=m;i++) if(!q[n][i]) ans++; if(ans) { printf("0\n%d",ans); return 0; } else { for(int i=1;i<=m;i++) s[i].l=999999999,s[i].r=0; for(int i=1;i<=m;i++) if(a[1][i]>=a[1][i-1]&&a[1][i]>=a[1][i+1]) { memset(q,0,sizeof(q)); q[1][i]=1; dfs(i,1,i); } sort(s+1,s+m+1,cmp); int i=m;while(s[i].l==999999999)i--; int tot=0; while(maxn<m){ int wwww=maxn; for(int j=1;j<=i;j++){ if(s[j].l<=maxn+1) wwww=max(s[j].r,wwww); } tot++; maxn=wwww; } printf("1\n%d",tot); } }