如果能够实现，每个河边的城市对应的控制区域一定是一条线段。
所以直接bfs每个河边的城市，贪心线段的右端点
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int qx[500005],qy[500005],a[505][505],n,m,bo[505][505],ans;//队列一定要开大！！！！！！
bool flag[505],ff[505];
struct WATER{
int l,r;
WATER(){l=r=0x7fffffff;}
}ww[505];
void bfs(int xx){
int h=1,t=1,x,y;
qx[1]=1; qy[1]=xx;
bo[1][xx]=xx;
while(h<=t){
x=qx[h]; y=qy[h++];
if((x-1>0)&&(bo[x-1][y]!=xx)&&(a[x-1][y]<a[x][y])){qx[++t]=x-1;qy[t]=y;bo[x-1][y]=xx;}
if((x+1<=n)&&(bo[x+1][y]!=xx)&&(a[x+1][y]<a[x][y])){qx[++t]=x+1;qy[t]=y;bo[x+1][y]=xx;}
if((y-1>0)&&(bo[x][y-1]!=xx)&&(a[x][y-1]<a[x][y])){qx[++t]=x;qy[t]=y-1;bo[x][y-1]=xx;}
if((y+1<=m)&&(bo[x][y+1]!=xx)&&(a[x][y+1]<a[x][y])){qx[++t]=x;qy[t]=y+1;bo[x][y+1]=xx;}
}
}
bool cmp(WATER a,WATER b){
if(a.l==b.l) return a.r<b.r;
return a.l<b.l;
}
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-1]<=a[1][i]&&a[1][i+1]<=a[1][i]){
bfs(i);
for(int j=1;j<=m;j++){
if(bo[n][j]==i){
flag[j]=1;
if(!ff[i]) ww[i].l=j,ff[i]=1;
ww[i].r=j;
}
}
}
}
for(int i=1;i<=m;i++)
if(!flag[i])
ans++;
if(ans){
printf("0\n%d\n",ans);
return 0;
}
sort(ww+1,ww+m+1,cmp);
int now=1,maxr=1,it=1,maxm=m;
for(int i=1;i<=m;i++)if(ww[i].l>m){maxm=i-1;break;}
while(now<m){
maxr=now+1;
for(int i=it;i<=maxm;i++){
if(ww[i].l>now+1) break;
if(ww[i].l<=now+1){
if(ww[i].r>=maxr){
maxr=ww[i].r;
it=i;
}
}
}
now=maxr; ans++;
}
printf("1\n%d\n",ans);
return 0;
}