记录编号	125490	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.097 s
提交时间	2014-10-08 20:57:47	内存使用	1.52 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m;
int ans;
bool fla=0;
bool bo[501];
bool flag[501][501];
int f[501];
int H[501][501];
int l[501],r[501];
void dfs(int,int,int);
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++) scanf("%d",&H[i][j]);
	}
	int sum=0;
	for(int i=1;i<=m;i++)
	{
		if(i>1 && H[1][i]<H[1][i-1]) continue;
		if(i<m && H[1][i]<H[1][i+1]) continue;
		dfs(i,1,i);
		if(i!=m) memset(flag,0,sizeof(flag));
	}
	for(int i=1;i<=m;i++)
	{
		if(!bo[i]) {fla=1;sum++;}
	}
	if(fla) {printf("0\n%d",sum);return 0;}
	else printf("1\n");
	for(int i=1;i<=m;i++)
	{
		for(int j=l[i];j<=r[i];j++)
		{
			if(f[j]>f[l[i]-1]+1 || !f[j])
				f[j]=f[l[i]-1]+1;
		}
	}
	printf("%d",f[m]);
}
void dfs(int s,int x,int y)
{
	if(x==n)
	{
		bo[y]=1;
		if(y<l[s] || !l[s]) l[s]=y;
		if(y>r[s]) r[s]=y;
	}
	int h=H[x][y];
	flag[x][y]=1;
	if(x<n && H[x+1][y]<h && !flag[x+1][y]) dfs(s,x+1,y);
	if(x>1 && H[x-1][y]<h && !flag[x-1][y]) dfs(s,x-1,y);
	if(y<m && H[x][y+1]<h && !flag[x][y+1]) dfs(s,x,y+1);
	if(y>1 && H[x][y-1]<h && !flag[x][y-1])	dfs(s,x,y-1);
}