记录编号	605025	评测结果	AAAAAAAAAA
题目名称	521.[NOIP 2010]引水入城	最终得分	100
用户昵称	彭欣越	是否通过	通过
代码语言	C++	运行时间	1.119 s
提交时间	2025-08-13 14:39:26	内存使用	5.03 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=510;
int dx[]={0,-1,1,0},dy[]={1,0,0,-1};
int n,m,sum,a[N][N],vis[N][N],mk[N];
struct node {
	int x,y;
};
struct edge {
	int l,r;
}s[N];
bool cmp (edge x,edge y) {
	return x.r>y.r;
}
queue<node>q;
void bfs (int x,int y,int k) {
	if (x==n) {
		mk[y]=1;
		s[y].l=y;
		s[y].r=y;
	}
	memset(vis,0,sizeof(vis));
	q.push((node){x,y});
	vis[x][y]=1;
	while (!q.empty()) {
		int x=q.front().x;
		int y=q.front().y;
		q.pop();
		for (int i=0;i<4;i++) {
			int xx=x+dx[i],yy=y+dy[i];
			if (xx<1||yy<1||xx>n||yy>m||a[xx][yy]>=a[x][y]||vis[xx][yy]) continue;
			if (xx==n) {
				mk[yy]=1;
				if (s[k].l==0) s[k].l=yy;
				else s[k].l=min(s[k].l,yy);
				s[k].r=max(s[k].r,yy);
			}
			vis[xx][yy]=1;
			q.push((node){xx,yy});
		}
	}	
}
void dfs (int idx) {
	//cout << idx <<endl;
	if (idx==m) return;
	for (int i=1;i<=m;i++) {
		if (s[i].l==0&&s[i].r==0) continue;
		if (s[i].l<=idx+1) {
			sum++;
	        dfs(s[i].r);
	        return;
		}
	}
}
int main () {
	freopen("flow.in","r",stdin);
	freopen("flow.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n >> m;
    //memset(l,0x3f,sizeof(l));
	//for (int i=1;i<=100000;i++) f[i]=i;
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			cin >> a[i][j];
		}
	}
	for (int i=1;i<=m;i++) bfs(1,i,i);
	//int sum=0;
	for (int i=1;i<=m;i++) if (mk[i]==0) sum++;
	if (sum>0) {
		cout << 0 <<endl;
		cout << sum <<endl;
		return 0;
	}
	cout << 1 <<endl;
    sort(s+1,s+1+m,cmp);
    //for (int i=1;i<=m;i++) cout << s[i].l <<' '<< s[i].r <<endl;
	dfs(1);
	cout << sum <<endl;
	return 0;
}