洛谷 P1434 [SHOI2002] 滑雪

// P1434 的**第一版**：纯 DFS，不记忆化。
//
// 题目：R × C 的高度矩阵，每步可以走到上下左右四个相邻格之一，**当且仅当高度会减小**。
//       求最长的一条滑坡（长度按**经过的格子数**算）。
//
// ⚠ 它**是对的**，只是把同一格重算了无数遍：从不同的高处滑下来都会经过它。
//   页面第 ② 步量了这个倍数 —— 而这道题的重复程度和数字三角形不是一个套路：
//   它取决于**地形**，不是取决于 n。

#include <bits/stdc++.h>
using namespace std;

static const int DX[4] = {-1, 1, 0, 0};
static const int DY[4] = {0, 0, -1, 1};

static int R, C;
static vector<vector<int>> h;
static long long calls = 0;

static int walk(int x, int y) {
    calls++;
    int res = 1;                            // 自己这一格
    for (int t = 0; t < 4; t++) {
        int nx = x + DX[t], ny = y + DY[t];
        if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
        if (h[nx][ny] >= h[x][y]) continue;  // ★ 只往**严格**更低处走
        res = max(res, 1 + walk(nx, ny));
    }
    return res;
}

int main(int argc, char** argv) {
    if (!(cin >> R >> C)) return 0;
    h.assign(R, vector<int>(C));
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) cin >> h[i][j];

    int ans = 0;
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) ans = max(ans, walk(i, j));
    cout << ans << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "calls=" << calls << "\n";
    return 0;
}

// P1434 滑雪 —— 记忆化搜索（★ 这一版就能 AC）
//
// 题目：R × C 的高度矩阵，每步可以走到上下左右四个相邻格之一，**当且仅当高度会减小**。
//       求最长的一条滑坡（长度按**经过的格子数**算）。
//
// ★★★ 这道题是「记忆化 vs 递推」这条分界线上**最干净的一个例子**，
//   而它干净在一句话上：**这张图的边不是「往某个固定方向」，是「往更低处」。**
//
//   数字三角形 / 过河卒的递推顺序是白送的 —— 「下一行」「上一行」就是顺序。
//   这道题呢？`f(x,y) = 1 + max(f(四个更低的邻居))`，
//   而「更低的邻居」可能在上下左右**任何一边** —— **没有现成的填表顺序**。
//   ⇒ 要写递推，得先**按高度排序**（页面第 ④ 步有那一版）；
//     而记忆化**根本不用管顺序**，递归自己会把依赖走对。
//
// ⚠ 这道题的递归**没有出口判断**也不会死循环：只往严格更低处走，高度严格递减，
//   走不了多少步就自然到头。⇒ 这一条是「高度严格减小」白送的，
//   页面第 ⑤ 步会看到把 `<` 写成 `<=` 会发生什么。

#include <bits/stdc++.h>
using namespace std;

static const int DX[4] = {-1, 1, 0, 0};
static const int DY[4] = {0, 0, -1, 1};

static int R, C;
static vector<vector<int>> h;
static vector<vector<int>> f;               // f[x][y] = 从 (x,y) 出发能滑几个格子；0 = 还没算
static long long calls = 0;

static int walk(int x, int y) {
    calls++;
    if (f[x][y]) return f[x][y];            // ★ 这里拿 0 当「没算过」是安全的：答案至少是 1
    int res = 1;                            // 自己这一格
    for (int t = 0; t < 4; t++) {
        int nx = x + DX[t], ny = y + DY[t];
        if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
        if (h[nx][ny] >= h[x][y]) continue;  // ★ 只往**严格**更低处走
        res = max(res, 1 + walk(nx, ny));
    }
    return f[x][y] = res;
}

int main(int argc, char** argv) {
    if (!(cin >> R >> C)) return 0;
    h.assign(R, vector<int>(C));
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) cin >> h[i][j];
    f.assign(R, vector<int>(C, 0));

    int ans = 0;
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) ans = max(ans, walk(i, j));
    cout << ans << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "calls=" << calls << "\n";
    return 0;
}

// P1434 的递推版：**先按高度从低到高排序**，再顺着填表。
//
// ★★★ 这一版存在的意义，是把「记忆化和递推到底差在哪」摆出来：
//
//   数字三角形、过河卒的填表顺序是**白送**的 ——「下一行」「上一行」本身就是顺序。
//   这道题不是：`f(x,y) = 1 + max(f(四个更低的邻居))`，
//   而「更低的邻居」可能在上下左右**任何一边**，没有现成的顺序可用。
//
//   ⇒ 要写递推，就得**自己造一个顺序**：把 R × C 个格子按高度**从低到高**排一遍，
//     再照这个顺序填 —— 轮到某一格时，比它低的格子必然都已经算完了。
//   ⇒ 而记忆化**根本不用管这件事**：递归自己会把依赖走对。
//
// ★ 这就是「什么时候该用记忆化」的一个可操作判据：
//   **当你说不出填表顺序的时候，用记忆化。**
//
// 代价：排序 `O(RC log(RC))`，比记忆化的 `O(RC)` 多一个 log（这道题 R, C ≤ 100，无所谓）。

#include <bits/stdc++.h>
using namespace std;

static const int DX[4] = {-1, 1, 0, 0};
static const int DY[4] = {0, 0, -1, 1};

int main() {
    int R, C;
    if (!(cin >> R >> C)) return 0;
    vector<vector<int>> h(R, vector<int>(C));
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) cin >> h[i][j];

    vector<int> id(R * C);
    for (int i = 0; i < R * C; i++) id[i] = i;
    sort(id.begin(), id.end(), [&](int a, int b) { return h[a / C][a % C] < h[b / C][b % C]; });

    vector<vector<int>> f(R, vector<int>(C, 1));
    int ans = 0;
    for (int p : id) {
        int x = p / C, y = p % C;
        for (int t = 0; t < 4; t++) {
            int nx = x + DX[t], ny = y + DY[t];
            if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
            if (h[nx][ny] >= h[x][y]) continue;          // 只看**严格**更低的邻居
            f[x][y] = max(f[x][y], f[nx][ny] + 1);       // ★ 它们一定已经算过了
        }
        ans = max(ans, f[x][y]);
    }
    cout << ans << "\n";
    return 0;
}

// P1434 的**错法**：把「只往**严格**更低处走」写成了「往不高于自己的地方走」。
//
// 题目：R × C 的高度矩阵，每步可以走到上下左右四个相邻格之一，**当且仅当高度会减小**。
//       求最长的一条滑坡（长度按**经过的格子数**算）。
//
// 题面原话：「一个人可以从某个点滑向上下左右相邻四个点之一，**当且仅当高度会减小**。」
//   —— 是**减小**，不是「不增加」。差一个等号。
//
// ⚠⚠ 而这个等号的代价不是「答案偏大」，是**程序直接崩掉**：
//   两个相邻的等高格子会**互相递归**，永远回不来 —— 段错误（爆栈）。
//   ★ 而官方样例里 25 个高度**两两不同**，它照样输出 25。
//   ⇒ 页面第 ⑤ 步量了「值域多小才会撞上等高的邻居」那条曲线。

#include <bits/stdc++.h>
using namespace std;

static const int DX[4] = {-1, 1, 0, 0};
static const int DY[4] = {0, 0, -1, 1};

static int R, C;
static vector<vector<int>> h;
static vector<vector<int>> f;               // f[x][y] = 从 (x,y) 出发能滑几个格子；0 = 还没算
static long long calls = 0;

static int walk(int x, int y) {
    calls++;
    if (f[x][y]) return f[x][y];            // ★ 这里拿 0 当「没算过」是安全的：答案至少是 1
    int res = 1;                            // 自己这一格
    for (int t = 0; t < 4; t++) {
        int nx = x + DX[t], ny = y + DY[t];
        if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
        if (h[nx][ny] > h[x][y]) continue;   // ★ 错在这里：等高也放行了
        res = max(res, 1 + walk(nx, ny));
    }
    return f[x][y] = res;
}

int main(int argc, char** argv) {
    if (!(cin >> R >> C)) return 0;
    h.assign(R, vector<int>(C));
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) cin >> h[i][j];
    f.assign(R, vector<int>(C, 0));

    int ans = 0;
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) ans = max(ans, walk(i, j));
    cout << ans << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "calls=" << calls << "\n";
    return 0;
}

// P1434 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1434Count`      人看的版本
// `./p1434Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 五段：
//   ① 官方样例：四个版本各输出什么（★ 那个错法在样例上也是 25）；
//   ② 不记忆化 vs 记忆化的调用次数 —— ★ 这道题的重复程度**取决于地形**，不取决于 n；
//   ③ ★★★ 和[同一章的 P1216](/sol/p1216/) 配成一对：
//      「省掉 vis、拿 0 当没算过」在那道题上把 O(n²) 打回 O(2ⁿ)，在这道题上**完全安全** ——
//      判据只有一句话：**这道题的答案不可能是 0**（一个格子自己就算 1 步）；
//   ④ 递推版（按高度排序后填表）和记忆化逐格相同；
//   ⑤ ★★★ 「等高也放行」那个错法：它的触发条件 ≡「图里有一对相邻等高格」，
//      而这件事的概率由**高度上限**说了算。

#include <bits/stdc++.h>
using namespace std;

static bool CSV = false;
static void row(const char* key, const vector<long long>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (long long x : v) printf(",%lld", x);
    printf("\n");
}

static const int DX[4] = {-1, 1, 0, 0};
static const int DY[4] = {0, 0, -1, 1};

static int R, C;
static vector<vector<int>> h, f;
static long long calls;
static bool blew;                            // ⑤ 用：递归深度超限（真程序在这里会爆栈）

/** memo = 是否记忆化；strict = 是否只往严格更低处走 */
static int walk(int x, int y, bool memo, bool strict, int depth = 0) {
    calls++;
    if (depth > 20000) { blew = true; return 1; }        // ⚠ 真程序没有这个上限，它会段错误
    if (blew) return 1;
    if (memo && f[x][y]) return f[x][y];
    int res = 1;
    for (int t = 0; t < 4; t++) {
        int nx = x + DX[t], ny = y + DY[t];
        if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
        if (strict ? (h[nx][ny] >= h[x][y]) : (h[nx][ny] > h[x][y])) continue;
        res = max(res, 1 + walk(nx, ny, memo, strict, depth + 1));
        if (blew) return 1;
    }
    if (memo) f[x][y] = res;
    return res;
}

static int solve(bool memo, bool strict, long long& outCalls) {
    f.assign(R, vector<int>(C, 0));
    calls = 0;
    blew = false;
    int ans = 0;
    for (int i = 0; i < R && !blew; i++)
        for (int j = 0; j < C && !blew; j++) ans = max(ans, walk(i, j, memo, strict));
    outCalls = calls;
    return blew ? -1 : ans;
}

/** 递推版：按高度从低到高填表 */
static int solveSort() {
    vector<int> id(R * C);
    for (int i = 0; i < R * C; i++) id[i] = i;
    sort(id.begin(), id.end(), [&](int a, int b) { return h[a / C][a % C] < h[b / C][b % C]; });
    vector<vector<int>> g(R, vector<int>(C, 1));
    int ans = 0;
    for (int p : id) {
        int x = p / C, y = p % C;
        for (int t = 0; t < 4; t++) {
            int nx = x + DX[t], ny = y + DY[t];
            if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
            if (h[nx][ny] >= h[x][y]) continue;
            g[x][y] = max(g[x][y], g[nx][ny] + 1);
        }
        ans = max(ans, g[x][y]);
    }
    return ans;
}

/** 图里有没有一对相邻的等高格 */
static bool hasEqualNeighbor() {
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            for (int t = 0; t < 4; t++) {
                int nx = i + DX[t], ny = j + DY[t];
                if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
                if (h[nx][ny] == h[i][j]) return true;
            }
    return false;
}

/** 和 p1434Gen.cpp 逐字一致 */
static void gen(int seed, int rr, int cc, int hi) {
    mt19937 rng((unsigned)seed * 2654435761u + 23u);
    R = rr > 0 ? rr : (int)(rng() % 6 + 3);
    C = cc > 0 ? cc : (int)(rng() % 6 + 3);
    if (rr > 0 && cc <= 0) C = (int)(rng() % 6 + 3);
    h.assign(R, vector<int>(C));
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) h[i][j] = (int)(rng() % (hi + 1));
}

static const char* SAMPLE =
    "1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9";

int main(int argc, char** argv) {
    CSV = (argc > 1 && string(argv[1]) == "csv");

    /* ① 官方样例 */
    {
        R = C = 5;
        h.assign(5, vector<int>(5));
        istringstream in(SAMPLE);
        for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) in >> h[i][j];
        long long c1, c2, c3;
        int memo = solve(true, true, c1);
        int brute = solve(false, true, c2);
        int eq = solve(true, false, c3);
        int srt = solveSort();
        if (!CSV) printf("① 官方样例：记忆化 %d（%lld 次调用）｜不记忆化 %d（%lld 次）"
                         "｜等高也放行 %d｜递推 %d\n", memo, c1, brute, c2, eq, srt);
        row("sample", {memo, c1, brute, c2, eq, srt});
    }

    /* ② 不记忆化 vs 记忆化：重复程度取决于地形 */
    {
        // ⚠ 蛇形那一档在 10 × 10 上要跑 21 亿次调用（度量程序光这一档就 13 秒）——
        //   缩到 8 × 8 就够说明问题了，倍数照样是七位数。
        if (!CSV) printf("\n② 不记忆化要多走多少（三种地形；★ 蛇形那档用 8 × 8，别的 10 × 10）\n");
        vector<long long> out;
        const char* NM[3] = {"随机高度", "蛇形单调递增", "一条对角线的斜坡"};
        for (int kind = 0; kind < 3; kind++) {
            R = C = (kind == 1) ? 8 : 10;
            h.assign(R, vector<int>(C));
            mt19937 rng(20260828u);
            for (int i = 0; i < R; i++)
                for (int j = 0; j < C; j++) {
                    if (kind == 0) h[i][j] = (int)(rng() % 10001);
                    else if (kind == 1) h[i][j] = (i % 2 == 0) ? i * C + j : i * C + (C - 1 - j);
                    else h[i][j] = i + j;
                }
            long long cm, cb;
            int a1 = solve(true, true, cm), a2 = solve(false, true, cb);
            out.push_back(cm); out.push_back(cb); out.push_back(a1);
            if (!CSV) printf("  %-14s：答案 %d（两版一致 %s）｜记忆化 %lld 次，不记忆化 %lld 次（%.1f 倍）\n",
                             NM[kind], a1, a1 == a2 ? "✓" : "✗", cm, cb, cb * 1.0 / cm);
        }
        row("terrain", out);
    }

    /* ③ ★★★ 「拿 0 当没算过」在这道题上为什么安全 */
    {
        int minF = INT_MAX, zeroCells = 0;
        for (int s = 1; s <= 300; s++) {
            gen(s, 0, 0, 10000);
            long long c;
            solve(true, true, c);
            for (int i = 0; i < R; i++)
                for (int j = 0; j < C; j++) { minF = min(minF, f[i][j]); if (f[i][j] == 0) zeroCells++; }
        }
        if (!CSV) printf("\n③ 300 张图、所有格子的 f 值：最小是 %d，等于 0 的有 %d 个\n"
                         "   ⇒ 答案不可能是 0（一个格子自己就算 1 步）"
                         "⇒ 这道题拿 0 当「没算过」是安全的（而 P1216 不是）\n", minF, zeroCells);
        row("zeroSafe", {minF, zeroCells});
    }

    /* ④ 递推版 ≡ 记忆化 */
    {
        int diff = 0;
        for (int s = 1; s <= 300; s++) {
            gen(s, 0, 0, 10000);
            long long c;
            if (solve(true, true, c) != solveSort()) diff++;
        }
        if (!CSV) printf("\n④ 递推（按高度排序后填表）和记忆化：300 张图不一致 %d 次\n", diff);
        row("sortSame", {diff});
    }

    /* ⑤ ★★★ 「等高也放行」：触发条件 ≡ 图里有一对相邻等高格 */
    {
        if (!CSV) printf("\n⑤ 「等高也放行」那个错法：300 张图里崩掉多少张（按高度上限分档）\n");
        vector<long long> out;
        for (int hi : {10000, 1000, 100, 20, 5, 2}) {
            int blowCnt = 0, eqCnt = 0, mismatch = 0;
            for (int s = 1; s <= 300; s++) {
                gen(s, 0, 0, hi);
                long long c;
                int bad = solve(true, false, c);
                bool eq = hasEqualNeighbor();
                if (bad < 0) blowCnt++;
                if (eq) eqCnt++;
                if ((bad < 0) != eq) mismatch++;      // ★ 两件事应该逐张相等
            }
            out.push_back(blowCnt); out.push_back(eqCnt); out.push_back(mismatch);
            if (!CSV) printf("  高度上限 %5d：崩掉 %3d / 300｜有相邻等高格的 %3d / 300｜两者对不上的 %d 张\n",
                             hi, blowCnt, eqCnt, mismatch);
        }
        row("eqCurve", out);
    }
    return 0;
}

// P1434 对拍生成器：`./p1434Gen <seed> [R] [C] [高度上限]`
//   R, C     默认 3 ~ 8
//   高度上限 默认 10000（照题面），★ **这个旋钮是这一页第 ⑤ 步的全部**
//
// ★★★ 这道题有一个错法是「把『严格更低』写成『不高于』」（p1434Eq.cpp），
//   它的触发条件干净得可以写成一句话：**图里存在一对相邻的等高格子。**
//   ⇒ 而照题面随机（高度 0 ~ 10000）时，小图上几乎撞不到 ——
//     页面第 ⑤ 步把「高度上限」从 10000 一路压到 2，量出了那条曲线。
//
// ⚠ 而这个错法的现形方式不是 WA，是**段错误**（两个等高格互相递归、爆栈）。
//   ⇒ 所以它**没有进 `check:viz` 的对拍**：让崩溃版进对拍会把对拍拖垮
//     （[第 5 章 P1042](/sol/p1042/) 量过：一次 abort 要 1.17 秒）。
//     那一档的数字由度量程序给出，它带递归深度上限。

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    mt19937 rng(seed * 2654435761u + 23u);
    int R = argc > 2 ? atoi(argv[2]) : (int)(rng() % 6 + 3);
    int C = argc > 3 ? atoi(argv[3]) : (int)(rng() % 6 + 3);
    int hi = argc > 4 ? atoi(argv[4]) : 10000;
    R = max(1, min(100, R));
    C = max(1, min(100, C));
    hi = max(1, min(10000, hi));

    printf("%d %d\n", R, C);
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) printf("%d%c", (int)(rng() % (hi + 1)), j == C - 1 ? '\n' : ' ');
    return 0;
}