记录编号	461952	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.847 s
提交时间	2017-10-20 22:10:22	内存使用	3.24 MiB

#include<bits/stdc++.h>//如果方案可行，那么他一定是连续一段 
using namespace std;
int n,m,a[505][505],f[505],book[505],vis[505][505],tot,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},b[505][505];
struct h{
	int l,r;
	h(){
		l=0x3fffffff;
		r=-l;
	}
	bool operator < (const h &o)const{
		return l<o.l;
	}
}e[505];
struct gg{
	int x,y;
	gg(){}
	gg(int a,int b){
		x=a;y=b;
	}
};
void bfs(int x){
	queue<gg>S;
	memset(vis,0,sizeof(vis));
	S.push(gg(1,x));vis[1][x]=1;
	while(!S.empty()){
		gg u=S.front();
		if(u.x==n){
			book[u.y]=1;
			e[x].l=min(u.y,e[x].l);
			e[x].r=max(u.y,e[x].r);
		}
		S.pop();
		for(int i=0;i<4;i++){
			int tem1=u.x+dx[i],tem2=u.y+dy[i];
			if(b[tem1][tem2]&&a[tem1][tem2]<a[u.x][u.y]&&!vis[tem1][tem2]){
				S.push(gg(tem1,tem2));
				vis[tem1][tem2]=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",&a[i][j]);
			b[i][j]=1;
		}
	}
	for(int i=1;i<=m;i++)bfs(i);
	int flag=0;
	for(int i=1;i<=m;i++){
		if(!book[i]){
			flag++;
		}
	}
	if(flag){
		cout<<0<<endl;
		cout<<flag;
		return 0;
	}
	else {
		memset(f,0x3f,sizeof(f));
		f[0]=0;
		sort(e+1,e+m+1);int now=1;
		for(int i=1;i<=m;i++){
			while(e[now].l==i&&now<=m){
				for(int j=e[now].l;j<=e[now].r;j++){
					f[j]=min(f[i-1]+1,f[j]);
				}
				now++;
			}
		}
		cout<<1<<endl<<f[m];
	}
	return 0;
}