记录编号	605026	评测结果	AAAAAAAAAA
题目名称	521.[NOIP 2010]引水入城	最终得分	100
用户昵称	ChenBp	是否通过	通过
代码语言	C++	运行时间	1.112 s
提交时间	2025-08-13 14:39:26	内存使用	4.59 MiB

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 505;
int n, m;
int h[MAXN][MAXN];
bool vis[MAXN][MAXN];
bool ok[MAXN][MAXN];
vector<pair<int, int>> xsc[MAXN];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
void bfs(int x, int y, int id) {
    memset(vis, false, sizeof(vis));
    queue<pair<int, int>> q;
    q.push({x, y});
    vis[x][y] = true;
    ok[x][y] = true;
    while (!q.empty()) {
        auto now = q.front();
        q.pop();
        int x = now.first, y = now.second;
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 1 && xx <= n && yy >= 1 && yy <= m) {
                if (!vis[xx][yy] && h[x][y] > h[xx][yy]) {
                    vis[xx][yy] = true;
                    ok[xx][yy] = true;
                    q.push({xx, yy});
                }
            }
        }
    }
    bool yy = 0;
    for (int i = 1; i <= m; i++) {
        if (vis[n][i]) {
            yy = 1;
            break;
        }
    }
    if (yy) {
        int l = m + 1, r = 0;
        for (int j = 1; j <= m; j++) {
            if (vis[n][j]) {
                l = min(l, j);
                r = max(r, j);
            }
        }
        if (l <= r) {
            xsc[id].push_back({l, r});
        }
    }
}
int main() {
    freopen("flow.in", "r", stdin);
    freopen("flow.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &h[i][j]);
        }
    }
    memset(ok, false, sizeof(ok));
    for (int j = 1; j <= m; j++) {
        bfs(1, j, j);
    }
    int cnt = 0;
    for (int j = 1; j <= m; j++) {
        if (!ok[n][j]) {
            cnt++;
        }
    }
    if (cnt > 0) {
        cout << 0 << endl << cnt;
    } else {
        vector<pair<int, int>> v;
        for (int i = 1; i <= m; i++) {
            for (auto i : xsc[i]) {
                v.push_back(i);
            }
        }
        sort(v.begin(), v.end());
        int tot = 0;
        int now = 1;
        int i = 0;
        while (now <= m) {
            int mr = 0;
            while (i < v.size() && v[i].first <= now) {
                mr = max(mr, v[i].second);
                i++;
            }

            tot++;
            now = mr + 1;
        }

        cout << 1 << endl << tot;
    }
    return 0;
}