记录编号	605059	评测结果	AAAAAAAAAA
题目名称	521.[NOIP 2010]引水入城	最终得分	100
用户昵称	我也不知道	是否通过	通过
代码语言	C++	运行时间	0.280 s
提交时间	2025-08-13 15:24:39	内存使用	6.65 MiB

#include <bits/stdc++.h>
using namespace std;
int n,m,h[501][501];
int ans=0;
int r[501][501]={0},l[501][501];
bool visit1[501][501]= {0};
int dfs(int x,int y) {
	int x1[4]= {0,0,-1,1},y1[4]= {-1,1,0,0};
	visit1[x][y]=1;
	for(int i=0; i<4; i++) {
		int xx=x+x1[i],yy=y+y1[i];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&h[xx][yy]<h[x][y]) {
			if(!visit1[xx][yy])	dfs(xx,yy);
			r[x][y]=max(r[x][y],r[xx][yy]);
			l[x][y]=min(l[x][y],l[xx][yy]);
		}
	}
	return 0;
}
int main() {
	freopen("flow.in", "r", stdin);
	freopen("flow.out", "w", stdout);
	cin >> n >>m;
	memset(l,600,sizeof(l));
	memset(r,0,sizeof(r));
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++){
         cin>>h[i][j];
         if(i==n)l[i][j]=r[i][j]=j;
     }
	}
	int L=1;
	for(int i=1; i<=m; i++) {
		if(!visit1[1][i]) dfs(1,i);
	}
	int R=0,Q=0;
	for(int i=1; i<=m; i++) {
		if(!visit1[n][i]) Q++;
	}
	if(Q) {
			cout<<0<<endl<<Q;
		return 0;
	}

	while(L<=m) {
		for(int i=1; i<=m; i++) {
			if(l[1][i]<=L) {
				R=max(R,r[1][i]);
			}
		}

		L=R+1;
		ans++;
	}
	cout<<1<<endl<<ans;
	return 0;
}