记录编号	458363	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	皓芷	是否通过	通过
代码语言	C++	运行时间	0.054 s
提交时间	2017-10-11 08:41:49	内存使用	4.15 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#define mysister
using namespace std;
const int maxn=501;
struct ad
{
	int l,r,h;
	ad(){l=502;r=0;}
	bool operator < (ad b)const
	{
	  return l==b.l?r>b.r:l<b.l;
	}
}a[maxn][maxn];
int vis[maxn][maxn],n,m,ans,last,len;
void in(int &x)
{
	x=0;char c=getchar();
	while(c<'0'||'9'<c)c=getchar();
	while('0'<=c&&c<='9'){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
}
void dfs(int i,int x,int y,int fax,int fay)
{
	vis[x][y]=1;
	if(x<n&&a[x][y].h>a[x+1][y].h)
	{
	  if(!vis[x+1][y])dfs(i,x+1,y,x,y);
	  else 
	  {
	  	a[x][y].l=min(a[x][y].l,a[x+1][y].l);
	    a[x][y].r=max(a[x][y].r,a[x+1][y].r);
	  }
	}
	if(y<m&&a[x][y].h>a[x][y+1].h)
	{
	  if(!vis[x][y+1])dfs(i,x,y+1,x,y);
	  else
	  {
	  	a[x][y].l=min(a[x][y].l,a[x][y+1].l);
	    a[x][y].r=max(a[x][y].r,a[x][y+1].r);
	  }
	}
	if(x>1&&a[x][y].h>a[x-1][y].h)
	{
	  if(!vis[x-1][y])dfs(i,x-1,y,x,y);
	  else
	  {
	  	a[x][y].l=min(a[x][y].l,a[x-1][y].l);
	    a[x][y].r=max(a[x][y].r,a[x-1][y].r);
	  }
	}
	if(y>1&&a[x][y].h>a[x][y-1].h)
	{
	  if(!vis[x][y-1])dfs(i,x,y-1,x,y);
	  else
	  {
	  	a[x][y].l=min(a[x][y].l,a[x][y-1].l);
	    a[x][y].r=max(a[x][y].r,a[x][y-1].r);
	  }
	}
	if(x==n)
	{
	  a[x][y].l=min(a[x][y].l,y);
	  a[x][y].r=max(a[x][y].r,y);
	}
	a[fax][fay].l=min(a[fax][fay].l,a[x][y].l);
	a[fax][fay].r=max(a[fax][fay].r,a[x][y].r);
}
int main()
{
	freopen("flow.in","r",stdin);
	freopen("flow.out","w",stdout);
	in(n);in(m);
	for(int i=1;i<=n;++i)
	  for(int j=1;j<=m;++j)
	    in(a[i][j].h);
	for(int i=1;i<=m;++i)
	  dfs(i,1,i,0,0);
	for(int i=1;i<=m;++i)
	  if(!vis[n][i])
	  	++ans;
	if(ans)
	  printf("0\n%d",ans);
	else
	{
	  printf("1\n");
	  //sort(a[1]+1,a[1]+m+1);
	  last=0;len=0;
	  for(int i=1;i<=m;++i)
	  {
	  	if(a[1][i].l>a[1][i].r)continue;//break;
	  	if(last+1<a[1][i].l)
	  	{
	  	  last=len;
		  ++ans;
		}
		if(last+1>=a[1][i].l&&a[1][i].r>len)
		{
		  len=a[1][i].r;
		}
	  }
	  if(len>last)++ans;
	  printf("%d",ans);
	}
	return 0;
}