【例9.24】滑雪

题目描述

给定 $R \times C$ （ $1 \leqslant R,C \leqslant 100$ ）的高度矩阵。从任意格子出发，每一步只能滑向上下左右相邻且高度严格减小的格子，路径长度按经过格子数计算。求最长滑坡长度。

输入：第一行 $R$ 、 $C$ ，接下来 $R$ 行每行 $C$ 个整数表示高度。
输出：一个整数，最长滑坡长度。

样例输入：

text

1
2
3
4
5
65 5
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

样例输出：

text

思路

设 $f(i,j)$ 为从 $(i,j)$ 出发的最长长度。严格递减的移动规则保证无环，按高度从小到大排序后依次填表：处理 $(i,j)$ 时所有更低邻居都已算完， $f(i,j)=1+\max$ 相邻更低格的 $f$ 值。全局最大值即为答案。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys

DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1))  # 上下左右四个相邻方向


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    R, C = next(data), next(data)
    grid = [[next(data) for _ in range(C)] for _ in range(R)]

    # 按高度从小到大处理：算 (r,c) 时，比它低的邻格必然已算完，
    # 等价于记忆化 dfs，但不需要递归（最长滑坡可达 R*C 级深度）。
    length: dict[tuple[int, int], int] = {}  # (r,c) -> 从该格出发的最长滑坡
    for h, r, c in sorted((grid[r][c], r, c) for r in range(R) for c in range(C)):
        lower = (  # 所有比当前格低、且在边界内的相邻格
            length[(r + dr, c + dc)]
            for dr, dc in DIRS
            if 0 <= r + dr < R and 0 <= c + dc < C and grid[r + dr][c + dc] < h
        )
        length[(r, c)] = 1 + max(lower, default=0)  # 一步都不滑也算了自身

    print(max(length.values()))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:50
 * update_at: 2026-10-05 07:50
 */

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 105;

int r, c;
int h[MAXN][MAXN];      // 每个格子的高度
int f[MAXN][MAXN];      // 从该格子出发的最长滑坡长度
int dr[4] = {-1, 1, 0, 0}; // 上下左右四个方向
int dc[4] = {0, 0, -1, 1};

struct Node {
    int h, x, y;
} nodes[MAXN * MAXN];

// 按高度升序排序，得到拓扑序
bool cmp(Node a, Node b) {
    return a.h < b.h;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> r >> c;
    int cnt = 0;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            cin >> h[i][j];
            cnt++;
            nodes[cnt].h = h[i][j];
            nodes[cnt].x = i;
            nodes[cnt].y = j;
        }
    }

    sort(nodes + 1, nodes + cnt + 1, cmp);

    int ans = 0;
    for (int k = 1; k <= cnt; k++) {
        int x = nodes[k].x;
        int y = nodes[k].y;
        f[x][y] = 1; // 至少包含自己
        for (int d = 0; d < 4; d++) {
            int nx = x + dr[d];
            int ny = y + dc[d];
            if (nx >= 1 && nx <= r && ny >= 1 && ny <= c && h[nx][ny] < h[x][y]) {
                // 邻居更低，且已经处理过（因为按高度升序）
                if (f[nx][ny] + 1 > f[x][y]) {
                    f[x][y] = f[nx][ny] + 1;
                }
            }
        }
        if (f[x][y] > ans) ans = f[x][y];
    }

    cout << ans << endl;
    return 0;
}

目录

题目描述

思路

参考代码