当前位置: 首页 > news >正文

蓝桥杯 滑行

原题目链接

滑行

📋 题目描述

小蓝准备在一个空旷的场地里面滑行,这个场地的高度不一,小蓝用一个 n n n m m m 列的矩阵来表示场地,矩阵中的数值表示场地的高度。

如果小蓝在某个位置,而他上下左右的某个位置的高度严格小于当前格子高度,他就可以滑过去,滑动距离记为 1。

如果上下左右所有位置的高度都大于等于当前格子的高度,小蓝的滑行就会结束。

小蓝可以任意选择一个起点开始滑行,问他最多能滑行多远(滑动的路径长度最大是多少)。


🧾 输入格式

  • 第一行两个整数 n m(1 ≤ n, m ≤ 100),表示矩阵的行与列。
  • 接下来 n 行,每行 m 个整数,表示高度(0 ≤ 高度 ≤ 10000)。

📤 输出格式

  • 输出一行一个整数,表示小蓝最多能滑行的距离(包括起点,路径长度)。

🧪 输入样例

6 8
18 20 16 14 13 11 5 0 
29 36 22 14 15 16 7 0 
32 31 30 14 13 11 5 0 
14 16 14 11 8 5 2 0 
7 10 12 10 5 2 0 0 
4 8 15 18 3 0 0 0

✅ 输出样例

10

💡 题解(思路解析)

✅ 解题关键:DFS + 记忆化搜索

由于小蓝可以从任意格子开始,并且滑行路径要遵守“当前高度 > 相邻格子高度”的规则,这很适合用**深度优先搜索(DFS)**来探索路径。

但如果我们直接暴力搜索每条路径,可能会重复遍历相同的子问题,效率低下。

因此我们使用记忆化搜索(Memoization),用一个 dp[i][j] 来存储从 (i,j) 出发的最长滑行路径。


🧠 算法步骤

  1. 初始化矩阵 arr 存储高度,dp 存储记忆化搜索结果。
  2. 遍历每一个点 (i, j),执行 dfs(i, j)
    • 如果当前点已经有 dp[i][j] 值,直接返回。
    • 否则向四个方向探索比当前高度低的点。
    • 递归调用 dfs(x, y) 并记录最大路径长度。
  3. 维护全局变量 ans,记录所有起点中滑行的最大值。

🧾 C++ 代码实现

#include<bits/stdc++.h>using namespace std;int ans = 0, n, m;
vector<vector<int>> arr(100, vector<int>(100, 0)), dir = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} }, dp = arr;int dfs(int i, int j) {if (dp[i][j] != 0) return dp[i][j];int res = 1, x, y;for (int k = 0; k < 4; k++) {x = i + dir[k][0], y = j + dir[k][1];if (x >= 0 && x < n && y >= 0 && y < m && arr[i][j] > arr[x][y]) res = max(res, 1 + dfs(x, y));}dp[i][j] = res;ans = max(ans, res);return res;
}int main() {cin >> n >> m;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) cin >> arr[i][j];}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) dfs(i, j);}cout << ans;return 0;
}//by wqs

📌 时间复杂度分析

  • 每个格子最多只会被 DFS 一次,之后都从 dp 中取值。
  • 总共有 n × m n \times m n×m 个格子,且每个格子最多向 4 个方向延伸。
  • 所以时间复杂度是:O(n × m),空间复杂度也是 O(n × m)。

🏷️ 标签

  • DFS 深度优先搜索
  • 记忆化搜索(动态规划)
  • 二维矩阵遍历
http://www.lryc.cn/news/578833.html

相关文章:

  • 蓝桥杯51单片机设计
  • 深入理解装饰器模式:动态扩展对象功能的灵活设计模式
  • [特殊字符] Excel 提取+图片批量插入 | Python 自动化生成稽查报告 Word 模板
  • 基于Java+SpringBoot的图书管理系统
  • 多云密钥统一管理实战:CKMS对接阿里云/华为云密钥服务
  • 分布式定时任务:Elastic-Job-Lite
  • GC393低功耗双电压比较器:精准、高效的信号处理解决方案
  • Axure版ArcoDesign 组件库-免费版
  • OpenCV CUDA模块设备层-----高效地计算两个uint 类型值的平均值函数vavg2()
  • Centos系统及国产麒麟系统设置自己写的go服务的开机启动项完整教程
  • 开源 | V3.1.1慧知开源重卡运营充电桩平台 - 重卡运营充电桩平台管理解决方案;企业级完整代码 多租户、模拟器、多运营商、多小程序;
  • Chrome 下载文件时总是提示“已阻止不安全的下载”的解决方案
  • DQL-1-基础查询
  • 技术学习_大语言模型
  • 大数据平台与数据中台:从概念到落地的系统化实践指南
  • day045-nginx跳转功能补充与https
  • 安全风险监测预警平台对企业的价值
  • 【AI智能体】基于Coze 制作高质量PPT实战操作详解
  • Android Native 之 inputflinger进程分析
  • flutter flutter_vlc_player播放视频设置循环播放失效、初始化后获取不到视频宽高
  • PyQt5-高级控件-容器StackedWidget
  • 学习笔记(29):训练集与测试集划分详解:train_test_split 函数深度解析
  • Servlet开发流程(包含IntelliJ IDEA项目添加Tomcat依赖的详细教程)
  • 玄机——某学校系统中挖矿病毒应急排查
  • 打造Docker Swarm集群服务编排部署指南:从入门到精通
  • 【公司环境下发布个人NPM包完整教程】
  • 网络协议概念与应用层
  • 解释LLM怎么预测下一个词语的
  • 图像二值化方法及 Python OpenCV 实现
  • 使用v-bind指令绑定属性