记录编号	605041	评测结果	AAAAAAAAAA
题目名称	521.[NOIP 2010]引水入城	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	0.254 s
提交时间	2025-08-13 14:56:32	内存使用	6.20 MiB

#include<iostream>
using namespace std;

const int MAXN = 1e3 + 5;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int n, m;
int map[MAXN][MAXN];
bool vis[MAXN][MAXN];
int idl[MAXN][MAXN], idr[MAXN][MAXN];

void dfs(int x, int y){
	vis[x][y] = 1;
	for(int i = 0;i < 4;i ++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(nx < 1 || ny < 1 || nx > n || ny > m || map[nx][ny] >= map[x][y]) continue;
		if(!vis[nx][ny]) dfs(nx, ny);
		idl[x][y] = min(idl[x][y], idl[nx][ny]);
		idr[x][y] = max(idr[x][y], idr[nx][ny]);
	}
}

int main(){
	freopen("flow.in","r",stdin);
	freopen("flow.out","w",stdout);
	cin >> n >> m;
	for(int i = 1;i <= n;i ++) for(int j = 1;j <= m;j ++) idl[i][j] = 1e9;
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			cin >> map[i][j];
			if(i == n){
				idl[i][j] = j;
				idr[i][j] = j;
			}
		}
	}
	for(int i = 1;i <= m;i ++){
		if(!vis[1][i]){
			dfs(1, i);
		}
	}
	int ans = 0;
	bool flag = 0;
	for(int i = 1;i <= m;i ++){
		if(!vis[n][i]){
			flag = 1;
			ans ++;
		}
	}
	if(flag){
		cout << 0 << '\n' << ans << '\n';
        return 0;
	}
	int l = 1, r = 0;
	ans = 0;
	while(l <= m){
		for(int i = 1;i <= m;i ++){
			if(idl[1][i] <= l){
				r = max(r, idr[1][i]);
			}
		}
		ans ++;
		l = r + 1;
	}
	cout << 1 << '\n' << ans << '\n';
	return 0;
}