关键词：DFS 、 记忆化搜索 、 动态规划

核心思想：使用DFS结合记忆化搜索来解决问题。记忆化搜索可以避免重复计算已经访问过的节点，从而提高效率。

解题步骤：

  1. 读取输入，初始化矩阵 mat 存储滑雪场的高度信息，初始化 dp 数组用于存储从每个位置出发的最长滑道长度。初始化 dx 和 dy 数组表示四个可能的移动方向。
  2. 定义 dfs(x, y) 函数，该函数返回从位置 (x, y) 开始的最长滑道长度。
  3. 如果 dp[x][y] 不为0，说明已经计算过，直接返回。否则，初始化 dp[x][y] 为1（即当前位置至少构成长度为1的滑道）。
  4. 尝试向四个方向移动，如果新位置 (nx, ny) 的高度低于当前位置，则递归调用 dfs(nx, ny) 并更新 dp[x][y]。
  5. 遍历所有位置，调用 dfs 函数并更新答案 ans。最后输出答案ans。

时间和空间复杂度：时间复杂度为 O(n * m * 4)，简化后为 O(n * m)；空间复杂度为 O(n * m)。

#include <iostream>
using namespace std;

// 定义常量，表示矩阵的最大尺寸
const int MAXN = 1e2 + 2;
// 定义四个方向的移动向量
int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
int n, m;
int mat[MAXN][MAXN]; 
int dp[MAXN][MAXN] = {0}; // 动态规划数组，存储从每个点出发的最大递增路径长度

int dfs(int x, int y) {
    if (dp[x][y] != 0) return dp[x][y]; // 如果已经计算过，直接返回结果
    dp[x][y] = 1; // 初始化路径长度为1（至少包含自身）
    
    // 遍历四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        // 检查新坐标是否在矩阵范围内，且高度是否递减
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (mat[nx][ny] <= mat[x][y]) continue;
        
        // 递归调用，更新从 (x, y) 出发的最大路径长度
        dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1);
    }
    return dp[x][y];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> mat[i][j];

    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            ans = max(ans, dfs(i, j)); // 计算从每个点出发的最大递增路径长度，并更新最终答案

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