记录编号	342424	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	残星誓言	是否通过	通过
代码语言	C++	运行时间	0.299 s
提交时间	2016-11-08 14:45:11	内存使用	3.19 MiB

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=500+10;
struct zb
{
	int x;int y;
};
struct qujian
{
	int l; int r;
	bool operator <(const qujian & b) const {
		if(l==b.l)
		return r>b.r;
		else
		return l<b.l;
	}
} c[maxn];
queue <zb> q;
int h[maxn][maxn];
bool vis[maxn][maxn];
int n,m;
int tot=0;
int tool[]={1,-1,0,0};
int tool2[]={0,0,-1,1};
int l[maxn][maxn];
int r[maxn][maxn];
int  bloodfill()
{
	while(!q.empty())
	{
		zb now=q.front(); q.pop(); vis[now.x][now.y]=1; //printf("%d %d \n",now.x,now.y);
		for(int i=0;i<=3;i++)
		{
			zb nx;  nx.x=now.x+tool[i];
					nx.y=now.y+tool2[i];
			if(!vis[nx.x][nx.y]&&nx.x>0&&nx.y>0&&nx.x<=n&&nx.y<=m&&h[nx.x][nx.y]<h[now.x][now.y])
				{
				q.push(nx);
				vis[nx.x][nx.y]=1;
					}
			}
	}
	for(int i=1;i<=m;i++)
		if(!vis[n][i]) tot++;
	return tot;
}
void floodfill(int x)
{
	while(!q.empty())
	{
		zb now=q.front(); q.pop();     
		if(!l[now.x][now.y])
		l[now.x][now.y]=x;                             
		for(int i=0;i<=3;i++)
		{
			zb nx;  nx.x=now.x+tool[i];
					nx.y=now.y+tool2[i];
			if(nx.x<=0||nx.y<=0||nx.x>n||nx.y>m) continue;
			if(l[nx.x][nx.y]==x) continue;				 //printf("2333333333333333");
			if(h[now.x][now.y]>=h[nx.x][nx.y]) continue;
			q.push(nx);                                
			if(nx.x!=1)
			{
				l[nx.x][nx.y]=x;
			}
				
		}
	}
}
void floodfill_r(int x)
{
	while(!q.empty())
	{
		zb now=q.front(); q.pop(); 
		if(!r[now.x][now.y])
		r[now.x][now.y]=x;                                          //printf("%d %d \n",now.x,now.y);
		for(int i=0;i<=3;i++)
		{
			zb nx;  nx.x=now.x+tool[i];
					nx.y=now.y+tool2[i];
			if(nx.x<=0||nx.y<=0||nx.x>n||nx.y>m) continue;
			if(r[nx.x][nx.y]==x) continue;
			if(h[now.x][now.y]>=h[nx.x][nx.y]) continue;
			q.push(nx);
			if(nx.x!=1)
			{
				r[nx.x][nx.y]=x;
			}
				
		}
	}
}
int work() 
{
	int tot=0;
	memset(l,0,sizeof(l));
	memset(r,0,sizeof(r));
	for(int i=1;i<=m;i++) if(!l[n][i]) 
	{	
		zb nx; nx.x=n; nx.y=i;
		q.push(nx);
		floodfill(i);
	}
	for(int i=m;i>=1;i--) if(!r[n][i])
	{
		zb nx; nx.x=n; nx.y=i;
		q.push(nx);
		floodfill_r(i);
	}
	for(int i=1;i<=m;i++) 
	{
		c[i].l=l[1][i];
		c[i].r=r[1][i];
		//printf("%d  l=%d r=%d\n",i,c[i].l,c[i].r);		
	}
	sort(c+1,c+1+m);
	int s=0,to=0;
	for(int i=1;i<=m;i++)
	{
		if(s+1>=c[i].l) to=max(to,c[i].r);
		else s=to,to=max(to,c[i].r),tot++;
	}
	if(s!=m) tot++;
	printf("1\n%d\n",tot);
	return 0;
	
}																
int main()
{
	freopen("flow.in","r",stdin);
	freopen("flow.out","w",stdout);
	scanf("%d%d",&n,&m);
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&h[i][j]);
	for(int i=1;i<=m;i++)
	{
		zb th; th.x=1; th.y=i;
		q.push(th);
	}
	if(bloodfill()) 
	{
		printf("0\n%d",tot);
		return 0;
	}
	else
	{
		return work();
	}

}