https://www.luogu.org/problemnew/show/P1514

题解：

BFS+排序+剪枝

对第一行的数据排序

按从大到小的顺序进行BFS，记录全部已经走过的格子和当前出发点可以走过的格子，记录当前出发点最后在最后一行的状态

因为可以证明区间一定连续。所以记录左右端点

然后最后一行不断暴力查找当前点为左端点的最大区间，直到完全覆盖

答案不存在时，暴力枚举最后一行是否有不能覆盖的点

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=500+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k;
int ans,cnt,flag,temp;
int a[N][N];
int b[][2]={1,0,0,1,-1,0,0,-1};
int vis[N][N];
int viss[N][N];
char str;
int l[N],r[N];
struct node {
    int v;
    int x,y;
    bool operator <(const node &S)const{
        return v>S.v;
    }
}e[N];
struct Node {
    int x,y;
}s,tmp,f;
void bfs(int x,int y){
    queue<Node>q;
    s.x=x;
    s.y=y;
    q.push(s);
    memset(vis,0,sizeof(vis));
    vis[s.x][s.y]=1;
    viss[s.x][s.y]=1;
    while(!q.empty()){
        f=q.front();
        q.pop();
        //cout<<f.x<<f.y<<endl;
        for(int i=0;i<4;i++){
            tmp.x=f.x+b[i][0];
            tmp.y=f.y+b[i][1];
            if(0<tmp.x&&tmp.x<=n&&0<tmp.y&&tmp.y<=m&&!vis[tmp.x][tmp.y]&&a[f.x][f.y]>a[tmp.x][tmp.y]){
                vis[tmp.x][tmp.y]=1;
                viss[tmp.x][tmp.y]=1;
                q.push(tmp);
            }
        }
    }
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d%d",&n,&m);
    //scanf("%d",&t);
    //while(t--){}
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    cnt=0;
    for(int i=1;i<=m;i++){
        e[i].v=a[1][i];
        e[i].x=1;
        e[i].y=i;
    }
    sort(e+1,e+m+1);
    for(int i=1;i<=m;i++){
        if(!viss[e[i].x][e[i].y]){
            bfs(e[i].x,e[i].y);//cout<<e[i].y<<" "<<r[i]<<" ";
            for(int j=1;j<=m;j++){
                if(vis[n][j]){
                    l[i]=j;
                    break;
                }
            }
            for(int j=1;j<=m;j++){
                if(vis[n][j]){
                    r[i]=j;
                }
            }

        }
    }
    flag=1;
    cnt=0;
        for(int j=1;j<=m;j++){
            if(!viss[n][j]){
                flag=0;
                cnt++;
            }
        }

    cout << flag << endl;
    if(flag){
        int left=1;
        while (left<=m){
            int maxr=0;
            for (int i=1;i<=m;i++)
                if (l[i]<=left)
                    maxr=max(maxr,r[i]);
            ans++;
            left=maxr+1;
            //cout<<left;
        }
        cout << ans << endl;
    }else{
        cout << cnt << endl;
    }

    //cout << "Hello world!" << endl;
    return 0;
}