记录编号	605119	评测结果	AAAAAAAAAA
题目名称	521.[NOIP 2010]引水入城	最终得分	100
用户昵称	会挽弯弓满月	是否通过	通过
代码语言	C++	运行时间	0.116 s
提交时间	2025-08-14 10:39:32	内存使用	5.91 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=510;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<48||c>57){
		if(c==45) f=-1;
		c=getchar();
	}
	while(c>=48&&c<=57){
		x=x*10+c-48;
		c=getchar();
	}
	return f*x;
}
int n,m;
int s[N][N];
bool edge(int h,int w){
	if(h<1||h>n) return 0;
	if(w<1||w>m) return 0;
	return 1;
}
bool vis[N][N];
int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};
int l[N][N],r[N][N];
void dfs(int x,int y){
	int tx,ty;
	for(int i=0;i<4;i++){
		tx=x+dx[i];
		ty=y+dy[i];
		if(!edge(tx,ty)) continue;
		if(s[x][y]<=s[tx][ty]) continue;
		if(!vis[tx][ty]){
			vis[tx][ty]=1;
			dfs(tx,ty);
		}
		l[x][y]=min(l[x][y],l[tx][ty]);
		r[x][y]=max(r[x][y],r[tx][ty]);
	}
	return;
}
void init(){

	for(int i=1;i<=m;i++){
		if(vis[1][i]) continue;
		vis[1][i]=1;
		dfs(1,i);
	}
	return;
}
int solve(){
	int id=1,maxx=0,ans=0;
	while(id<=m){
		for(int i=1;i<=m;i++){
			if(l[1][i]<=id) maxx=max(maxx,r[1][i]);
		}
		id=maxx+1;
		ans++;
	}
	return ans;
}
int main(){
	freopen("flow.in","r",stdin);
	freopen("flow.out","w",stdout);
	n=read();m=read();
	memset(l,0x3f,sizeof(l));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			s[i][j]=read();
			if(i==n) l[i][j]=r[i][j]=j;
		}
	}
	init();
	bool flag=0;
	int ans=0;
	for(int i=1;i<=m;i++){
		if(!vis[n][i]){
			flag=1;
			ans++;
		}
	}
	if(flag){
		printf("0\n%d",ans);
		return 0;
	}
	ans=solve();
	printf("1\n%d",ans);
	return 0;
}