链接：1631. 最小体力消耗路径
题解：https://leetcode-/problems/path-with-minimum-effort/solution/duo-tu-xiang-xi-fen-xi-jie-ti-si-lu-fen-7z89x/
https://leetcode-/problems/path-with-minimum-effort/solution/zui-xiao-ti-li-xiao-hao-lu-jing-by-zerotrac2/
class Solution {private:vector<vector<int>> direction{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};bool dfs(vector<vector<int>>& grid, int row, int col, vector<vector<bool>>& visited, int val) {int m = grid.size();int n = grid[0].size();visited[row][col] = true;for(int i = 0; i < 4; ++i) {int next_row = row + direction[i][0];int next_col = col + direction[i][1];// check是否超过边界，并且当前路线是否满足<=valif(next_row < 0 || next_row >= m || next_col < 0 || next_col >= n || visited[next_row][next_col] || abs(grid[next_row][next_col]-grid[row][col]) > val) {continue;}// 到达重点。表示val数值可以if(next_row == m-1 && next_col == n-1) {return true;}// 搜索下一层if(dfs(grid, next_row, next_col, visited, val)) {return true;}}return false;}public:int minimumEffortPath(vector<vector<int>>& heights) {if(heights[0].size() == 1 && heights.size() == 1) {return 0;}int low = 0;int high = 1000000;while(low < high) {int mid = (high+low)/2;vector<vector<bool>> visited(heights.size(), vector<bool>(heights[0].size(), false));// 如果mid可以，需要继续缩小边界if(dfs(heights, 0, 0, visited, mid)) {high = mid;} else {low = mid+1;}}return low;}};
如果觉得《1631. 最小体力消耗路径》对你有帮助，请点赞、收藏，并留下你的观点哦！
