记录编号	294507	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.721 s
提交时间	2016-08-12 13:46:19	内存使用	10.08 MiB

#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 1510
using namespace std;
int h[maxn][maxn];
int n,m;
int sum;
int l[maxn],r[maxn],dp[maxn];
bool f,flag[maxn][maxn],judge[maxn];
/* h储存读入 
sum用来储存多少不能供水 f用来判断能否全部供水； 
flag用于dfs时判是否visited 
l，r 记录的是以第一行的i为起点 到的最后一行的连续的点的l-r区间
*/
void dfs(int s,int x,int y)//s是从第一行开始最多能到最后一行多少个点  坐标为h[x][y] 
{
	if(x==n)
	{
		judge[y]=1;//到了第n行 可以到y 更新judge 
		if(y<l[s]||!l[s])l[s]=y;//如果l[s]=0更新 或者l[s]<y 
		if(y>r[s])r[s]=y;//这里记录的l,r数组记录的是以第一行的s为起点能到的最后一行的连续的点的l-r区间用于求第二问 
	}
	int hi=h[x][y];flag[x][y]=1;
	if(x<n && h[x+1][y]<hi && !flag[x+1][y])dfs(s,x+1,y);//floodfill 
	if(x>1 && h[x-1][y]<hi && !flag[x-1][y])dfs(s,x-1,y);
	if(y<m && h[x][y+1]<hi && !flag[x][y+1])dfs(s,x,y+1);
	if(y>1 && h[x][y-1]<hi && !flag[x][y-1])dfs(s,x,y-1);
}
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]);
		}
	}
	//对于第一问 dfs可以解决
	for(int i=1;i<=m;i++)
	{		
		if(i>1 && h[1][i]<h[1][i-1])continue;//为什么要continue呢？ 如果这个点比旁边的两个任何一个水站低，那么他们可以
		//给自己，就不用dfs这个点了，这就可以避免重复计算  
		if(i<m && h[1][i]<h[1][i+1])continue;//判断第一行   因为第一行直接可以得到水  判断i边界 
		memset(flag,0,sizeof(flag));//清空上次的标记 
		dfs(i,1,i);//找出能到达的最后一行最多的点 
	}
	for(int i=1;i<=m;i++)
	{
		if(!judge[i])
		{
			sum++;f=1;//如果最后一行有没到的 那么就sum++，通知f=1； 
		}
	} 
	if(f){//没到 
		puts("0");printf("%d\n",sum);
		fclose(stdin);fclose(stdout);
	}
	else
	{
		puts("1");
	}
	//开始dp求第二问 
	/*
	 dp之前要先证明一个东西QwQ  即通过dfs找出来的到达的最后一行的点都是连续的，这样我们dfs记录的l，r数组才敢用
	 证明： 假设最后一行的这些点不是连续的  那么我们随意取l-r中间一个不能到的点为x ，那么x一定比旁边的点都高 ，
	 那么你怎么可能有解？？？ 直接输出0别求第二问了； 
	 所以证明完了之后变成了dp求线段覆盖型的动归 
	*/ 
	for(int i=1;i<=m;i++)
	{
		for(int j=l[i];j<=r[i];j++)
		{
			if(dp[j]>dp[ l[i]-1 ]+1 || !dp[j])//dp[j]如果是0那么肯定要更新啊， 
			{
				dp[j]=dp[ l[i]-1 ]+1;//到达n行j列所需的机器> 到达n行l[i]-1列所需的机器+1 更新QwQ； 
			}
		}
	}
	printf("%d",dp[m]);//到第m列最少用几台机器 
	fclose(stdin);
	fclose(stdout);
	return 0;
}