记录编号	125276	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.712 s
提交时间	2014-10-08 07:48:07	内存使用	1.53 MiB

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cstdio>

#define Maxn 503
#define clean(x, y) memset(x, y, sizeof(x))
#define INF 0x7fffffff

using namespace std;

struct node {int x, y;} line[Maxn] = {0};
queue <node> q;

int n, m, h[Maxn][Maxn] = {0};
bool v[Maxn] = {0}, flag[Maxn][Maxn] = {0};
int f[Maxn] = {0};

const int xx[4] = {0, 0, 1, -1};
const int yy[4] = {1, -1, 0, 0};

void flood(int now, int x, int y) { //把本题化为线段的最小代价覆盖 
    if (x > n || x < 1 || y > m || y < 1) return;
    if (x == n) {
		v[y] = true; //种子填充法 
		if (line[now].x == 0 || line[now].x > y) {
			line[now].x = y;
		}
		if (line[now].y == 0 || line[now].y < y) {
			line[now].y = y;
		}	
	}
    flag[x][y] = true;
    if (!flag[x + 1][y] && h[x + 1][y] < h[x][y]) flood(now, x + 1, y);
    if (!flag[x][y + 1] && h[x][y + 1] < h[x][y]) flood(now, x, y + 1);
    if (!flag[x - 1][y] && h[x - 1][y] < h[x][y]) flood(now, x - 1, y);
    if (!flag[x][y - 1] && h[x][y - 1] < h[x][y]) flood(now, x, y - 1);
}

bool cmp (const node a, const node b) {return a.y < b.y;}

void init() {
	cin >> n >> m;
	for (int i = 1;i <= n;i ++) {
		for (int j = 1;j <= m;j ++) {
			cin >> h[i][j];
		}
	}
	for (int i = 1;i <= m;i ++) {
		memset(flag, 0, sizeof(flag));
		flood(i, 1, i);
	}
	bool judge = true;
	for (int i = 1;i <= m;i ++) { //先填充一遍，看是否可行 
		 judge = judge && v[i];
	}
	if (!judge) {
		int tot = 0;
		cout << '0' << endl;
		for (int i = 1;i <= m;i ++) {
			if (!v[i]) tot ++; //直接统计输出 
		}
		cout << tot << endl;
		return ;
	} else {
		cout << '1' << endl;
		sort(line + 1, line + m + 1, cmp); //以y为关键字排序
		int tmp = 1;
		f[0] = 0;
		for (int i = 1;i <= m;i ++) {
			if (i >= line[tmp].y) {
				while (tmp <= m && line[tmp].y < i) tmp ++;
				while (i == line[tmp].y) { //剪裁线段
					if (line[tmp].x == 1 || f[line[tmp].x - 1] != 0) {
						if (f[i] == 0 || f[i] > f[line[tmp].x - 1] + 1) {
							f[i] = f[line[tmp].x - 1] + 1;
						}
					}
					tmp ++;
				}
				if (f[i] != 0) {
					for (int j = 1;j < i;j ++) {
						if (f[j] == 0 || f[j] > f[i]) {
							f[j] = f[i];
						} //化为前缀
					}
				}
			}
		}
		cout << f[m] << endl;
	}
}

int main() {
	freopen("flow.in", "r", stdin);
	freopen("flow.out", "w", stdout);
	ios :: sync_with_stdio(false);
	init();
	return 0;
}