题解 | #滑雪#

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

int map[101][101], dp[101][101] = {0};//dp存储从每个点开始的最长滑道
int n, m;

//采用记忆化dfs
int dfs(int i, int j) {
    int res = 1;
    int direct = 4;
    if(dp[i][j])return dp[i][j];//已经搜索过，直接返回
    //上
    if (i > 0 && map[i - 1][j] < map[i][j]) {
        if (!dp[i - 1][j])dp[i - 1][j] = dfs(i - 1, j);//如果上面的点未搜索，搜索并记录
        res = max(res, dp[i - 1][j] + 1);
    }
    //右
    if (j < m - 1 && map[i][j + 1] < map[i][j]) {
        if (!dp[i][j + 1])dp[i][j + 1] = dfs(i, j + 1);
        res = max(res, dp[i][j + 1] + 1);
    }
    //下
    if (i < n - 1 && map[i + 1][j] < map[i][j]) {
        if (!dp[i + 1][j])dp[i + 1][j] = dfs(i + 1, j);
        res = max(res, dp[i + 1][j] + 1);
    }
    //左
    if (j > 0 && map[i][j - 1] < map[i][j]) {
        if (!dp[i][j - 1])dp[i][j - 1] = dfs(i, j - 1);
        res = max(res, dp[i][j - 1] + 1);
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    int maxt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            maxt = max(maxt, dfs(i, j));
        }
    }
    printf("%d", maxt);
}
// 64 位输出请用 printf("%lld")