下山

题目

人要一直往上走，除非你在山顶要回家。

很快到了郊游的日子，这一次小J和小R来到了龙泉山。很快他们爬到了山顶，他们发现龙泉山变成了 n 行 m 列的矩形，每一个方块上都有它的高度。

小R这个时候并不是很想回家："小J，你可以帮我找到最长的下山路径吗？"

小J想了想，决定还是需要请你来帮忙。

在一片 n 行 m 列的山地上，每一块土地都有自己的高度，小J和小R需要回家，每一次只能走向相邻的土地，并且只能向下走或者向高度一样的土地走，请你帮助小J找到不管从哪个地方出发他们最多可以走过多少块土地。

输入：第一行两个整数 n, m，n 表示有多少行，m 表示有多少列。接下来 n 行，每行 m 个数，表示每块土地的高度。
输出：一个整数，表示最长的下山距离。

样例1：

5 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

25

样例2：

3 4
1 2 3 4
4 3 2 1
5 6 7 8

8

提示：对于 30% 的数据，保证 n≤10, m≤10。对于 60% 的数据，保证 n≤100, m≤100。对于 100% 的数据，保证 n≤500, m≤500。

思路

对每个格子 f(r,c) 表示从该格子出发能走过的最多格子数。 转移为 f(r,c) = 1 + max(f(nr,nc))，其中 (nr,nc) 是四方向中高度 ≤ 当前的邻居。 用记忆化 DFS：每次计算前先查 memo[r][c]，算过了直接返回，避免重复搜索。 对所有格子跑一遍 DFS，取最大值即为答案。

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

int n, m;
int h[505][505];
int memo[505][505];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int dfs(int r, int c) {
    if (memo[r][c] != 0) return memo[r][c];

    memo[r][c] = 1;
    for (int k = 0; k < 4; k++) {
        int nr = r + dx[k];
        int nc = c + dy[k];
        if (nr>=0&&nr<n&&nc>=0&&nc<m&&h[nr][nc]<=h[r][c]) {
            memo[r][c] = max(memo[r][c], 1+dfs(nr,nc));
        }
    }
    return memo[r][c];
}

int main() {
    cin >> n >> m;
    for (int c1 = 0; c1 < n; c1++)
        for (int c2 = 0; c2 < m; c2++)
            cin >> h[c1][c2];

    int ans = 0;
    for (int c1 = 0; c1 < n; c1++)
        for (int c2 = 0; c2 < m; c2++)
            ans = max(ans, dfs(c1,c2));

    cout << ans << "\n";
    return 0;
}

复杂度分析

• 时间复杂度：O(nm)，每个格子最多计算一次。
• 空间复杂度：O(nm)，memo 数组与递归栈。

← 返回菜鸟的coding