记录编号	605087	评测结果	AAAAAAAAAA
题目名称	521.[NOIP 2010]引水入城	最终得分	100
用户昵称	xxz	是否通过	通过
代码语言	C++	运行时间	0.203 s
提交时间	2025-08-13 19:44:41	内存使用	18.06 MiB

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,h[1234][1234],l[1234][1234],r[1234][1234],ans=0,flag=0,dx[]={-1,0,1,0},dy[]={0,1,0,-1};
bool vis[1234][1234];
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x*f;
}
void dfs(int x,int y) {
	for(int i=0;i<4;i++) {
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<1||nx>n||ny<1||ny>m||h[x][y]<=h[nx][ny]) continue;
		if(!vis[nx][ny]) vis[nx][ny]=1,dfs(nx,ny);
		l[x][y]=min(l[x][y],l[nx][ny]),r[x][y]=max(r[x][y],r[nx][ny]);
	}
}
signed main() {
	n=read(),m=read();
	memset(l,0x3f,sizeof(l));
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {
		h[i][j]=read();
		if(i==n) l[i][j]=r[i][j]=j;
	}
	for(int i=1;i<=m;i++) if(!vis[1][i]) vis[1][i]=1,dfs(1,i);
	for(int i=1;i<=m;i++) if(!vis[n][i]) flag=1,ans++;
	if(flag) {
		printf("0\n%lld",ans);
		return 0;
	}
	int idx=1; ans=0;
	while(idx<=m) {
		int maxx=0;
		for(int i=1;i<=m;i++) if(l[1][i]<=idx) maxx=max(maxx,r[1][i]);
		ans++,idx=maxx+1;
	}
	printf("1\n%lld",ans);
}