三、完整代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespACe std;
const int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; // 四个方向
int dfs(vector<vector<int>>& matrix, vector<vector<int>>& memo, int i, int j) {
if(memo[i][j] != 0) return memo[i][j]; // 已计算过
int max_len = 1; // 至少包含自己
for(auto& dir : dirs) {
int x = i + dir[0], y = j + dir[1];
// 边界检查且高度必须严格递减
if(x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size()
&& matrix[x][y] < matrix[i][j]) {
max_len = max(max_len, dfs(matrix, memo, x, y) + 1);
}
}
memo[i][j] = max_len; // 记忆化存储
return max_len;
}
int longestSkiPath(vector<vector<int>>& matrix) {
if(matrix.empty()) return 0;
int n = matrix.size(), m = matrix[0].size();
vector<vector<int>> memo(n, vector<int>(m, 0)); // 记忆化数组
int res = 0;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
res = max(res, dfs(matrix, memo, i, j));
}
}
return res;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> matrix(n, vector<int>(m));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
cin >> matrix[i][j];
}
}
cout << longestSkiPath(matrix) << endl;
return 0;
}
memo数组:存储每个点出发的最长滑道长度,避免重复计算
DFS递归:从当前点向四个方向探索,只向更低点移动
终止条件:当无法继续下降时返回1(只包含自己)
五、优化与扩展
剪枝优化:可以先对高点排序,从高到低处理
并行计算:独立计算不同起点的路径
路径记录:修改算法可输出具体路径
这个解决方案完美结合了DFS的直观性和动态规划的高效性,是处理矩阵路径类问题的经典模式。