本文主要是介绍代码随想录1631最小体力值消耗，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。请你返回从左上角走到右下角的最小 体力消耗值 。
解题思路
二分查找来确定最小的体力消耗值。首先初始化一个左边界left为0，一个右边界right为1e6（题目中给出的最大高度差）。然后在每次查找过程中，计算出中间值mid，并使用深度优先搜索来判断是否存在一条路径，其中相邻格子之间的高度差绝对值不超过mid。如果存在一条路径，则将right更新为mid，否则将left更新为mid + 1。最终返回left作为最小的体力消耗值。
在深度优先搜索的过程中，我们使用一个visited数组来记录已经访问过的格子，避免重复访问。通过递归的方式，我们可以依次尝试上下左右四个方向的移动，并判断是否满足条件。如果能够到达右下角的格子，则返回true，否则返回false。
代码实现
class Solution {
public:
int minimumEffortPath(vector<vector>& heights) {
int rows = heights.size();
int cols = heights[0].size();
vector<vector> visited(rows, vector(cols, false));
int left = 0;
int right = 1e6; // 最大高度差为1e6
while (left < right) {int mid = left + (right - left) / 2;if (dfs(heights, visited, 0, 0, mid)) {right = mid;} else {left = mid + 1;}// 重置visited数组visited = vector<vector<bool>>(rows, vector<bool>(cols, false));}return left;
}
private:
bool dfs(vector<vector>& heights, vector<vector>& visited, int row, int col, int maxDiff) {
int rows = heights.size();
int cols = heights[0].size();
if (row == rows - 1 && col == cols - 1) {return true;}visited[row][col] = true;// 上下左右四个方向vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};for (const auto& dir : directions) {int newRow = row + dir.first;int newCol = col + dir.second;if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols&& !visited[newRow][newCol]&& abs(heights[row][col] - heights[newRow][newCol]) <= maxDiff) {if (dfs(heights, visited, newRow, newCol, maxDiff)) {return true;}}}return false;
}
};
这篇关于代码随想录1631最小体力值消耗的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
