记录编号	125791	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.614 s
提交时间	2014-10-10 07:34:16	内存使用	1.42 MiB

/*
	author	:hzoi_ztx
	title	:cogs 521 [NOIP2010] 引水入城
	ALG		:贪心。。dp 
	comment	:f[i]表示以线段i为结尾的连接到1的最少线段数
			 f[i] = min(f[j]+1) ;
			 (line[j].s<line[i].s && line[j].t>=line[i].s-1)
			 f[0] = 0 ; line[0].s = 0 ; line[0].t = 0 ;
*/

#include <cstdio>
#include <cstring>
#include <algorithm>

#define  maxn	520
#define  maxm	520
#define  info	0x3f3f3f3f

const int dx[4] = {-1 , 1 , 0 , 0 } ;
const int dy[4] = {0 , 0 , -1 , 1 } ;

struct seg{
	int s , t ;
	seg() { s = t = info ; }
	void update(int p) {
		if (t==info || p>t) t = p ;
		if (s==info || p<s) s = p ;
	}
	bool operator < (const seg a) const { 
		return s < a.s ;
	}
} line[maxm] ;

bool visit[maxn][maxn] ;
bool flag[maxn] = {false} ;

int n , m , ans = 0 ;
int h[maxn][maxm] ;
int f[maxm] ;

void fill(int x,int y,int p) {
	if (x<1 || y<1 || x>n || y>m) return ;
	if (x == n) {
		flag[y] = true ; line[p].update(y) ;
	}
	visit[x][y] = true ;
	/*for (int i = 0 ; i < 4 ; i ++ )
		if (!visit[x+dx[i]][y+dy[i]] && h[x][y]>h[x+dx[i]][y+dy[i]])
			fill(x+dx[i] , y+dy[i] , p) ;*/
	if(!visit[x+1][y] && h[x+1][y] < h[x][y]) fill(x+1, y, p);
    if(!visit[x][y+1] && h[x][y+1] < h[x][y]) fill(x, y+1, p);
    if(!visit[x-1][y] && h[x-1][y] < h[x][y]) fill(x-1, y, p);
    if(!visit[x][y-1] && h[x][y-1] < h[x][y]) fill(x, y-1, p);
    ////这么不科学的事!!!!!!!!!! 
}

void dp() {
	putchar('1') ;
	std::sort(line+1 , line+m+1) ;
	memset(f , 0x3f , sizeof (f)) ;
	ans = info ;
	int i , j ;
	f[0] = 0 ; line[0].s = 0 ; line[0].t = 0 ;
	for (i = 0 ; i <= m ; i ++ ) {
		if (line[i].s == info) break ; //可能一些蓄水厂不能将水引向另一岸 
		for (j = i+1 ; j <= m ; j ++ ) {
			if (line[j].s > line[i].t+1) break ;
			if (f[i]+1 < f[j]) f[j] = f[i]+1 ;
		}
		//printf("\n%d: %d->%d",i,line[i].s,line[i].t) ;
		if (line[i].t==m && f[i]<ans) ans = f[i] ;
	}
}

int main() {
	#define  READ
	#ifdef   READ
		freopen("flow.in" ,"r",stdin ) ;
		freopen("flow.out","w",stdout) ;
	#endif
	scanf("%d%d", &n , &m ) ;
	int i , j ;
	for (i = 1 ; i <= n ; i ++ )
		for (j = 1 ; j <= m ; j ++ )
			scanf("%d", &h[i][j] ) ;
	for (j = 1 ; j <= m ; j ++ ) {
		memset(visit , 0 , sizeof (visit)) ;
		fill(1 , j , j) ;
	}
	for (j = 1 ; j <= m ; j ++ )
		if (!flag[j])
			ans ++ ;
	if (ans) putchar('0') ;
	else dp() ;
	printf("\n%d\n", ans ) ;
	return 0 ;
}