题面描述

塔子哥是一位极限滑雪爱好者，他希望探索滑雪场的最长路径。给定一个滑雪场的高度矩阵，要求滑雪路径从一个点滑向周围的相邻点，且下一个点的高度必须严格低于当前点。输入包括矩阵的行数和列数，以及每个点的高度。输出最长的滑雪路径长度。你是否想要了解具体的解题思路或方法？

题解：记忆化搜索

定义$f[i][j]$表示以$(i,j)$点开始的最大路径，由于只能向比它权值低的点走，因此对于所有可以前往的路径$(a,b)$

应该有$f[i][j]=max(f[i][j],f[a][b]+1)$

初始化所有的$f[i][j]=-1$，然后对于每一个点$(i,j)$，跑一遍DFS，加一个记忆化搜索的判断

方法步骤

1. 定义数据结构：

   • 使用二维数组 g 存储滑雪场的高度。
   • 使用二维数组 f 存储从每个点出发的最大路径长度，初始值设为 -1 表示尚未计算。

2. DFS 函数：

   • 通过递归的方式计算以 (x, y) 为起点的最大路径长度。如果已经计算过（f[x][y] != -1），直接返回已存储的结果。
   • 否则，将路径长度初始化为 1（包括当前点）。
   • 检查四个方向（上、下、左、右），如果相邻点高度低于当前点，递归调用 DFS 计算相邻点的最大路径长度，并更新当前点的最大路径长度。

3. 主函数：

   • 输入滑雪场的高度信息。
   • 对于每个点调用 DFS 函数，计算并更新最大路径长度。

4. 输出结果：

   • 最后，输出所有点中找到的最长路径长度。

if(f[i][j]!=-1){   //说明该点已经被访问过 直接返回
    return f[i][j];
}

C++

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

const int N=210; // 定义最大数组大小
int g[N][N], n, m, f[N][N]; // g 存储高度, f 存储最大路径长度
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1}; // 四个方向的偏移量

// 深度优先搜索函数
int dfs(int x, int y) {
    // 如果已经计算过，直接返回结果
    if(f[x][y] != -1) return f[x][y];
    f[x][y] = 1; // 当前点的路径长度至少为 1
    int t = 0; // 用于记录下方可达的最大路径长度

    // 遍历四个相邻的方向
    for(int i = 0; i < 4; i++) {
        int a = dx[i] + x, b = dy[i] + y; // 计算相邻点的坐标
        // 检查边界条件和高度条件
        if(a < 0 || a >= n || b < 0 || b >= m || g[a][b] >= g[x][y]) continue;
        // 递归 DFS 计算相邻点的路径长度
        t = max(t, dfs(a, b));
    }
    
    f[x][y] += t; // 更新当前点的路径长度
    return f[x][y]; // 返回当前点的最大路径长度
}

int main() {
    cin >> n >> m; // 输入滑雪场的行列数
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> g[i][j]; // 输入每个点的高度
        }
    }
    
    memset(f, -1, sizeof f); // 初始化路径长度数组
    int res = 1; // 记录最长路径，初始为 1

    // 对每个点调用 DFS 计算最大路径长度
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            res = max(res, dfs(i, j)); // 更新最长路径
        }
    }
    
    cout << res << endl; // 输出结果
    return 0;
}

Java

import java.util.*;

public class Main {
    // 定义滑雪场的高度数组和记忆化数组
    static int[][] g = new int[210][210]; // g[i][j]表示(i,j)点的高度
    static int[][] f = new int[210][210]; // f[i][j]表示从(i,j)开始的最大滑雪路径长度
    static int n, m; // n为行数，m为列数
    // 四个方向的偏移量，分别是上、下、左、右
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, 1, -1};

    // 深度优先搜索函数
    static int dfs(int x, int y) {
        // 如果该点的最大路径长度已经计算过，直接返回
        if (f[x][y] != -1) return f[x][y];
        f[x][y] = 1; // 初始化路径长度为1（包括当前点）
        int t = 0; // 用于记录可达的最大路径长度

        // 遍历四个相邻的方向
        for (int i = 0; i < 4; i++) {
            int a = dx[i] + x, b = dy[i] + y; // 计算相邻点的坐标
            // 检查边界条件和高度条件，确保只向低于当前高度的点滑动
            if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] >= g[x][y]) continue;
            // 递归调用DFS函数计算相邻点的最大路径长度
            t = Math.max(t, dfs(a, b));
        }

        // 更新当前点的最大路径长度
        f[x][y] += t;
        return f[x][y]; // 返回当前点的最大路径长度
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建输入扫描器
        n = sc.nextInt(); // 输入行数
        m = sc.nextInt(); // 输入列数
        // 输入每个点的高度
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j] = sc.nextInt();
            }
        }

        // 初始化记忆化数组f为-1，表示尚未计算
        for (int i = 0; i < n; i++) {
            Arrays.fill(f[i], -1); // 将每一行的所有值设置为-1
        }

        int res = 1; // 记录最长路径长度，初始为1
        // 对每个点调用DFS函数计算最大路径长度
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                res = Math.max(res, dfs(i, j)); // 更新最长路径
            }
        }

        // 输出最长滑雪路径长度
        System.out.println(res);
    }
}

Python3

# 读取行数 n 和列数 m
n, m = map(int, input().split())
# 读取滑雪场的高度矩阵 g
g = [list(map(int, input().split())) for _ in range(n)]
# 初始化记忆化数组 f，用于存储每个点的最大路径长度，初始值为 -1
f = [[-1] * m for _ in range(n)]
# 定义四个方向的偏移量：上、下、左、右
dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]

# 深度优先搜索函数
def dfs(x, y):
    # 如果该点的最大路径长度已经计算过，直接返回
    if f[x][y] != -1:
        return f[x][y]
    
    # 初始化当前点的路径长度为 1（包括当前点）
    f[x][y] = 1
    t = 0  # 用于记录可达的最大路径长度

    # 遍历四个相邻的方向
    for i in range(4):
        a, b = dx[i] + x, dy[i] + y  # 计算相邻点的坐标
        # 检查边界条件和高度条件，确保只向低于当前高度的点滑动
        if a < 0 or a >= n or b < 0 or b >= m or g[a][b] >= g[x][y]:
            continue  # 跳过不满足条件的点
        
        # 递归调用 DFS 函数计算相邻点的最大路径长度
        t = max(t, dfs(a, b))
    
    # 更新当前点的最大路径长度
    f[x][y] += t
    return f[x][y]  # 返回当前点的最大路径长度

res = 1  # 记录最长路径，初始为 1
# 对每个点调用 DFS 函数计算最大路径长度
for i in range(n):
    for j in range(m):
        res = max(res, dfs(i, j))  # 更新最长路径

# 输出最长滑雪路径长度
print(res)

题目描述

小明是一个喜欢探索极限的滑雪家, 他热衷于探索怎样才能使滑雪的路径最长

小明从滑雪场的一个点滑向另一个点需要两个要求 :

1 : 另一个点在小明当前点的附近 (前, 后, 左, 右)

2 : 另一个点的高度严格小于当前点

输入描述

给定长为 $R$, 宽为 $C$ 的滑雪场

接下来 $R$ 行, 每行 $C$ 个数字, 表示滑雪场每个点的高度

$1\le R,C\le 200$

$0 \le Grid[i][j] \le 2^{31} - 1$

输出描述

最长的滑雪路径长度

样例

输入

3 3
9 6 4
5 6 7
2 1 1

输出

5

说明

最长的滑雪路径为[7,6,5,2,1]，因此这条路径的节点的个数为5