记录编号	42205	评测结果	AAAEAEEEEE
题目名称	[NOIP 2010]引水入城	最终得分	40
用户昵称	王者自由	是否通过	未通过
代码语言	C++	运行时间	0.549 s
提交时间	2012-09-17 11:48:46	内存使用	3.20 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500 + 10;
int n, m, s, G[N][N];
bool v[N][N];
struct line {
    int s, t;
} l[N];
void flood(int x, int y) {
    if(x > n || x < 1 || y > m || y < 1) return;
    v[x][y] = 1;
    if(!v[x+1][y] && G[x+1][y] < G[x][y]) flood(x+1, y);
    if(!v[x][y+1] && G[x][y+1] < G[x][y]) flood(x, y+1);
    if(!v[x-1][y] && G[x-1][y] < G[x][y]) flood(x-1, y);
    if(!v[x][y-1] && G[x][y-1] < G[x][y]) flood(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", G[i]+j);
    for(int i=1; i<=m; i++)
        flood(1, i);
    for(int i=1; i<=m; i++)
        s += !v[n][i];
    if(s) {
        printf("0\n%d\n", s);
    } else { 
        for(int i=1; i<=m; i++) {
            memset(v, 0, sizeof(v));
            flood(1, i);
            for(int j=1; j<=m; j++)
                if(v[n][j]) {
                    l[i].s = j, l[i].t = m;
                    for(int k=j+1; k<=m; k++)
                        if(!v[n][k]) { l[i].t = k - 1; break; }
                    break;
                }
        } s = 0;
        for(int i=1, k=1, t=0; k<=m; )
            if(l[i].s <= k) {
                t = max(t, l[i++].t);
                if(t > m) { s++; break; }
            } else k = t + 1, s++, t = 0;
        printf("1\n%d\n", s);
    }
    return 0;
}