记录编号	445534	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	Regnig Etalsnart	是否通过	通过
代码语言	C++	运行时间	0.400 s
提交时间	2017-09-06 10:28:13	内存使用	2.07 MiB

#include<cstdio>
#include<cstring> 
#include<queue>
#define INF 0x7fffffff
using namespace std;
struct NODE{int x,y;}Node[250001];
struct DSC{int l,r;}g[501];
int n,m,pic[501][501],vis[501][501],col[501],f[501],cnt,ans1,ans2,i,j;
queue<NODE>q;
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
void work(int x,int y)
{
	NODE b;b.x=x;b.y=y;
	q.push(b);vis[x][y]=1;
}
void bfs(NODE a)
{
	memset(vis,0,sizeof(vis));
	q.push(a);vis[a.x][a.y]=1;
	while(!q.empty())
	{
		NODE now=q.front();q.pop();
		int x=now.x,y=now.y;
		if(x==1)col[a.y]=1;
		if((!vis[x-1][y])&&(pic[x-1][y]>pic[x][y]))work(x-1,y);
		if((!vis[x+1][y])&&(pic[x+1][y]>pic[x][y]))work(x+1,y);
		if((!vis[x][y-1])&&(pic[x][y-1]>pic[x][y]))work(x,y-1);
		if((!vis[x][y+1])&&(pic[x][y+1]>pic[x][y]))work(x,y+1);
	}
}
void dfs(int x,int y,int num)
{
	if(x==n)
	{
		g[num].l=min(g[num].l,y);
		g[num].r=max(g[num].r,y);
	}
	vis[x][y]=1;
	if((!vis[x-1][y])&&(pic[x-1][y]<pic[x][y]))dfs(x-1,y,num);
	if((!vis[x+1][y])&&(pic[x+1][y]<pic[x][y]))dfs(x+1,y,num);
	if((!vis[x][y-1])&&(pic[x][y-1]<pic[x][y]))dfs(x,y-1,num);
	if((!vis[x][y+1])&&(pic[x][y+1]<pic[x][y]))dfs(x,y+1,num);	
	vis[x][y]=0;
}
int Main()
{
	freopen("flow.in","r",stdin);freopen("flow.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)
	{
		scanf("%d",&pic[i][j]);
		Node[++cnt].x=i;
		Node[cnt].y=j;
	}
	for(i=1;i<=m;i++)
	{
		NODE a;a.x=n;a.y=i;
		bfs(a);
		if(!col[i])ans2++;
	}
	if(ans2)
	{
		printf("0\n%d\n",ans2);
		return 0;
	}
	printf("1\n");
	for(i=1;i<=m;i++)
	{
		f[i]=INF;
		g[i].l=INF;g[i].r=0;
		memset(vis,0,sizeof(vis));
		dfs(1,i,i);
	}
	for(i=1;i<=m;i++)for(j=1;j<=m;j++)
      if(i>=g[j].l&&i<=g[j].r)f[i]=min(f[i],f[g[j].l-1] + 1);
    printf("%d\n",f[m]);
	return 0;
}
int main(){;}
int syy=Main();