首页 > 试题广场 >

滑雪

[编程题]滑雪
  • 热度指数：4008 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个 的矩阵，矩阵中的数字表示滑雪场各个区域的高度，你可以选择从任意一个区域出发，并滑向任意一个周边的高度严格更低的区域（周边的定义是上下左右相邻的区域）。请问整个滑雪场中最长的滑道有多长？(滑道的定义是从一个点出发的一条高度递减的路线）。
(本题和矩阵最长递增路径类似，该题是当年NOIP的一道经典题)

数据范围： ，矩阵中的数字满足

输入描述:
第一行输入两个正整数 n 和 m 表示矩阵的长宽。
后续 n 行输入中每行有 m 个正整数，表示矩阵的各个元素大小。



输出描述:
输出最长递减路线。

示例1

输入

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

输出

25

说明

从25出发，每次滑向周边比当前小 1 的区域。 25->24->23->22->......->1
算法知识视频讲解
开通博客
头像 Coming680
发表于 2022-03-02 16:46:23
直接dfs+动态规划解决 #include<iostream> #include<cstring> using namespace std; int graph[100][100],dp[100][100]; void dfs(int n,int m,int row,int 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 静寂旮旯
发表于 2022-04-24 17:05:22
解题思路： 关键点，是找到起始的位置，在输入地图的同时，把点(i,j)的高度和其坐标保存下来pointshight(i,j)points_{hight(i,j)}pointshight(i,j)​,再将points按照hight排序。那么拍完序以后的内容就是我们要处理点的顺序。 接下来只要对于po 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 1eHz
发表于 2024-10-27 02:14:21
关键词：DFS 、 记忆化搜索 、 动态规划核心思想：使用DFS结合记忆化搜索来解决问题。记忆化搜索可以避免重复计算已经访问过的节点，从而提高效率。解题步骤：读取输入，初始化矩阵 mat 存储滑雪场的高度信息，初始化 dp 数组用于存储从每个位置出发的最长滑道长度。初始化 dx 和 dy 数组表示四 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 wwwkal
发表于 2022-04-19 22:33:03
dfs+回溯 对于点[i,j]，其最长路径由上下左右四个点决定。递归求解周围四点即可。由于路径严格递减，故不用担心无限循环的情况。 #include<iostream> using namespace std; const int MAXN = 105; int n, m; int m 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 有礼貌的山羊追赶太阳
发表于 2025-04-11 21:22:15
import java.util.*; // 这题求的是长度，每次+1 public class Main { static int[][] dirs = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public static v 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 ZyWoOoO
发表于 2025-05-14 17:35:06
#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 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 勤劳的小蜗牛许愿简历通过
发表于 2024-11-06 11:11:45
#include <iostream> #include<cstring> using namespace std; int n, m; const int N = 110; int h[N][N]; int f[N][N]; int dx[4] = {-1, 0, 1, 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Zongwei_Qin
发表于 2024-03-19 20:26:33
#include <algorithm> #include <cstdio> #include <iostream> using namespace std; int map[101][101], dp[101][101] = {0};//dp存储从每个点开始的 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 _Bingbong
发表于 2024-12-18 22:35:53
解题思路 这是一个求矩阵中最长递减路径的问题，可以通过记忆化搜索来解决： 对于矩阵中的每个点，都可以作为起点 从每个点出发，可以向上下左右四个方向移动，但要求移动到的点的高度严格小于当前点 使用记忆化数组来存储每个点作为起点的最长路径长度，避免重复计算 最终答案是所有点作为起点的最长路径中的最大值 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 凶狠跑刀崽
发表于 2025-06-22 23:16:21
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new S 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 记忆化搜索 图 拓扑排序 递归
难度：
8条回答 5954浏览

热门推荐

通过挑战的用户

查看代码

相关试题

滑雪

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号