记录编号	141303	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	席一鸣	是否通过	通过
代码语言	C++	运行时间	0.260 s
提交时间	2014-11-30 17:10:56	内存使用	1.52 MiB

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
bool l[501][501],w[501];
int e[501][501],f[501],m,n;
class s
{
	public:
		int l,r;
		s()
		{
			l=0x7fffffff;
			r=0;
		}
}a[501];
bool operator<(s a,s b)
{
	return a.r<b.r;
}
void o(int s,int x,int y)
{
	int h;
	if(x==n)
	{
		w[y]=1;
		a[s].l=min(a[s].l,y);
		a[s].r=max(a[s].r,y);
	}
	l[x][y]=1;
	h=e[x][y];
	if(x<n&&e[x+1][y]<h&&!l[x+1][y])
		o(s,x+1,y);
	if(x>1&&e[x-1][y]<h&&!l[x-1][y])
		o(s,x-1,y);
	if(y<m&&e[x][y+1]<h&&!l[x][y+1])
		o(s,x,y+1);
	if(y>1&&e[x][y-1]<h&&!l[x][y-1])
		o(s,x,y-1);
}
main()
{
	freopen("flow.in","r",stdin);
	freopen("flow.out","w",stdout);
	int i,j,x=0,t=1;
	cin>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			cin>>e[i][j];
	for(i=1;i<=m;i++)
	{
		if(i>1&&e[1][i]<e[1][i-1])
			continue;
		if(i<m&&e[1][i]<e[1][i+1])
			continue;
		memset(l,0,sizeof(l));
		o(i,1,i);
	}
	for(i=1;i<=m;i++)
		if(w[i])
			x++;
	if(x<m)
	{
		cout<<"0\n"<<m-x;
		return 0;
	}
	sort(a+1,a+1+m);
	for(i=1;i<=m;i++)
		f[i]=0x7fffffff/2;
	for(i=1;i<=m;i++)
	{
		if(i<a[t].r)
			continue;
		while(t<=m&&i>a[t].r)
			t++;
		while(i==a[t].r)
			f[i]=min(f[i],f[a[t++].l-1]+1);
		for(j=1;j<i;j++)
			f[j]=min(f[j],f[i]);
	}
	cout<<"1\n"<<f[m];
}