记录编号	515727	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	Chtholly	是否通过	通过
代码语言	C++	运行时间	0.115 s
提交时间	2018-10-23 08:54:49	内存使用	2.27 MiB

#include<bits/stdc++.h>
#define map MAP
#define maxn 505
using namespace std;
struct Node{
	int l,r;
	bool operator < (const Node &Next) const{
		return l < Next.l;
		return r < Next.r;
	}
} con[maxn],d[maxn];
int n,m,pd,num,total;
int a[maxn][maxn],map[maxn][maxn],cover[maxn];
void dfs(int x,int y,int rt){
	if(x<1||x>n||y<1||y>m) return ;
	map[x][y]=true;
	if(x==n) cover[y]=1,con[rt].l=min(con[rt].l,y),con[rt].r=max(con[rt].r,y);
	if(a[x][y]>a[x+1][y]&&map[x+1][y]!=1&&x!=n) dfs(x+1,y,rt);
    if(a[x][y]>a[x-1][y]&&map[x-1][y]!=1&&x!=1) dfs(x-1,y,rt);
    if(a[x][y]>a[x][y+1]&&map[x][y+1]!=1&&y!=m) dfs(x,y+1,rt);
    if(a[x][y]>a[x][y-1]&&map[x][y-1]!=1&&y!=1) dfs(x,y-1,rt);
}
int main()
{
	freopen("flow.in","r",stdin);
	freopen("flow.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(i==1) con[j].l=0x7ffffff;
			scanf("%d",&a[i][j]);
		}
	for(int i=1;i<=m;i++)
		if(a[1][i-1]<=a[1][i]&&a[1][i+1]<=a[1][i]) dfs(1,i,i),memset(map,0,sizeof(map));
	for(int i=1;i<=m;i++) if(cover[i]==0) num++;
	if(num!=0){cout<<"0"<<'\n'<<num;return 0;}
	cout<<"1"<<'\n';
	for(int i=1;i<=m;i++)
		if(con[i].l!=0x7ffffff&&con[i].r!=0) 
			d[++total].l=con[i].l,d[total].r=con[i].r;
	sort(d+1,d+total+1);
	int x=1,y=1,ans=0;
	while(y<=m){
	    int z=0;
	    while(d[x].l<=y) 
			z=max(z,d[x].r),x++;
	    y=z+1,ans++;
	}
	cout<<ans<<endl;
}