题目描述

找最长的滑雪距离,每一个点都对应一个滑雪距离哦

C++ 代码

//
// Created by zrz on 2021/4/17.
//
#include <iostream>
#include <cstring>
using namespace std;
//记忆化搜索 = dp + 深搜

int n,m;
const int N = 310;
int g[N][N];//记录每一点的高度
int f[N][N];//记忆化数组,代表从当前格子出发的最大滑雪 长度

int dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1};

int dp(int x,int y)//把(x,y)作为起点进行深搜,返回更新后的该点的最大滑雪距离
{
    if (f[x][y] != -1)//如果当前格子已经划过了
        return f[x][y];//返回当前格子出发的最大滑雪长度,不重复计算,减少时间复杂度

    f[x][y] = 1;//如果没走过,先至少走一个格子,如果下一步走不了,那当前格子就是终点,1就是他的长度
    for (int i = 0;i < 4;i ++)//遍历他能走到的点
    {
        int a = x + dx[i],b = y + dy[i];
        if (a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b])//如果能走就走,就不断递归,其实是深搜
            f[x][y] = max(f[x][y],dp(a,b) + 1);//比下一层递归的点多走一格,因为他是从下往上更新的
    }
    return f[x][y];
}

int main()
{
    //1.输入,初始化图
    cin >> n >> m;
    for (int i = 1;i <= n;i ++)
        for (int j = 1;j <= m;j ++)
            cin >> g[i][j];//先输入图

    memset(f, -1, sizeof f);//把记忆化数组初始化为-1,表示没走过

    //取最大滑雪距离
    int res = 0;//取max之前,将答案初始化为小值,避免干扰
    for (int i = 1;i <= n;i ++)//把每个点作为起点
        for (int j = 1;j <= m;j ++)
            res = max(res,dp(i,j));//取最大的滑雪距离

    //3.输出        
    cout << res << endl;
}