题解 | 滑雪

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> dp(100,vector(100,1));//动态规划
vector<vector<int>> graph(100,vector(100,1));
void dfs(int n,int m,int row,int col);
int main() {
    int n,m;
    cin>>n>>m;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>graph[i][j];
        }
    }
    //使用深度优先填充dp,维护最大值
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dfs(n,m,i,j);
            ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans;
    return 0;
    //
}
//深度优先搜索
void dfs(int n,int m,int row,int col){
    //上
    if(row-1>=0 && graph[row-1][col]<graph[row][col]){
        dfs(n,m,row-1,col);
        dp[row][col]=max(dp[row-1][col]+1,dp[row][col]);
    }
    //下
    if(row+1<n && graph[row+1][col]<graph[row][col]){
        dfs(n,m,row+1,col);
        dp[row][col]=max(dp[row+1][col]+1,dp[row][col]);
    }
    //左
    if(col-1>=0 && graph[row][col-1]<graph[row][col]){
        dfs(n,m,row,col-1);
        dp[row][col]=max(dp[row][col-1]+1,dp[row][col]);
    }
    //右
    if(col+1<m && graph[row][col+1]<graph[row][col]){
        dfs(n,m,row,col+1);
        dp[row][col]=max(dp[row][col+1]+1,dp[row][col]);
    }
}
// 64 位输出请用 printf("%lld")