题解 | #滑雪#

dfs+回溯
对于点[i,j]，其最长路径由上下左右四个点决定。递归求解周围四点即可。由于路径严格递减，故不用担心无限循环的情况。

#include<iostream>

using namespace std;
const int MAXN = 105;
int n, m;
int map[MAXN][MAXN];
int dplen[MAXN][MAXN];

int dfs(int i, int j, int pre){
    if(i < 0 || i == n || j < 0 || j == m)//边界情况
        return 0;
    if(pre <= map[i][j])    //严格递减
        return 0;
    if(dplen[i][j] != 0)    //保证只访问一次map[i][j]，故时间复杂度为O(nm)
        return dplen[i][j];
    int cur = 0;    //若此点为低谷，即四周都没有路，那么长度为0
    cur = max(cur, dfs(i-1, j, map[i][j]));
    cur = max(cur, dfs(i+1, j, map[i][j]));
    cur = max(cur, dfs(i, j-1, map[i][j]));
    cur = max(cur, dfs(i, j+1, map[i][j]));
    dplen[i][j] = cur + 1;        //路径+1，保证取得最长的路径
    return dplen[i][j];
}

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 mmax = 1;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)    //遍历，并求最长路径长度
            mmax = max(mmax, dfs(i, j, 1005));  //最大高度不超过1000
    cout << mmax;
    
    return 0;
}