题解 | 滑雪

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1001;
int f[MAXN][MAXN];
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
int dp[MAXN][MAXN]; // 记忆化数组
int n, m;

int dfs(int x, int y) {
    if (dp[x][y] != 0) return dp[x][y]; // 已计算过，直接返回
    int max_step = 1; // 初始为1，自身算一步
    for (int i = 0; i < 4; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (f[x][y] > f[nx][ny]) {
            max_step = max(max_step, dfs(nx, ny) + 1); // 递归并更新最大步数
        }
    }
    dp[x][y] = max_step; // 保存结果
    return max_step;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> f[i][j];
        }
    }
    int maxx = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            maxx = max(maxx, dfs(i, j)); // 计算每个点的最长路径
        }
    }
    cout << maxx << endl;
    return 0;
}