蓝桥杯 滑行
原题目链接
滑行
📋 题目描述
小蓝准备在一个空旷的场地里面滑行,这个场地的高度不一,小蓝用一个 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)
出发的最长滑行路径。
🧠 算法步骤
- 初始化矩阵
arr
存储高度,dp
存储记忆化搜索结果。 - 遍历每一个点
(i, j)
,执行dfs(i, j)
:- 如果当前点已经有
dp[i][j]
值,直接返回。 - 否则向四个方向探索比当前高度低的点。
- 递归调用
dfs(x, y)
并记录最大路径长度。
- 如果当前点已经有
- 维护全局变量
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 深度优先搜索
- 记忆化搜索(动态规划)
- 二维矩阵遍历