LeetCode 1631. 最小体力消耗路径（DFS + 二分查找）

Michael阿明

发布于 2021-02-19 12:41:38

5030

发布于 2021-02-19 12:41:38

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。

一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。

你每次可以往上，下，左，右四个方向之一移动，你想要找到耗费 体力最小的一条路径。

一条路径耗费的体力值是路径上相邻格子之间 高度差绝对值的最大值 决定的。

请你返回从左上角走到右下角的最小体力消耗值 。

示例 1：

输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
输出：2
解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优，因为另一条路劲差值最大值为 3 。

示例 2：

输入：heights = [[1,2,3],[3,8,4],[5,3,5]]
输出：1
解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。

示例 3：

输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
输出：0
解释：上图所示路径不需要消耗任何体力。
 
提示：
rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10^6

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/path-with-minimum-effort 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：

LeetCode 1102. 得分最高的路径（优先队列BFS/极大极小化二分查找）

LeetCode 410. 分割数组的最大值（极小极大化二分查找）

LeetCode 774. 最小化去加油站的最大距离（极小极大化二分查找）

LeetCode 875. 爱吃香蕉的珂珂（二分查找）

LeetCode LCP 12. 小张刷题计划（二分查找）

LeetCode 1011. 在 D 天内送达包裹的能力（二分查找）

LeetCode 1062. 最长重复子串（二分查找）

LeetCode 5438. 制作 m 束花所需的最少天数（二分查找）

LeetCode 5489. 两球之间的磁力（极小极大化二分查找）

套路二分模板题

class Solution {
    int m, n;
    vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        m = heights.size(), n = heights[0].size();
        int l = 0, r = 1e6, mid, ans = 0;
        while(l <= r)
        {
            mid = l + ((r-l)>>1);
            vector<vector<bool>> vis(m, vector<bool>(n,false));
            if(dfs(heights, vis, 0, 0, mid))//有一条路径相邻的数字差都小于mid
            {
                r = mid-1;
                ans = mid;
            }
            else
                l = mid+1;
        }
        return ans;
    }
    bool dfs(vector<vector<int>>& heights, vector<vector<bool>>& vis, int x, int y, int d)
    {
        if(x == m-1 && y == n-1)
            return true;
        vis[x][y] = true;
        int i, j, k;
        for(k = 0; k < 4; k++)
        {
            i = x + dir[k][0];
            j = y + dir[k][1];
            if(i>=0 && i<m && j>=0 && j<n && !vis[i][j]
                    && abs(heights[x][y]-heights[i][j]) <= d)
            {
                if(dfs(heights, vis, i, j, d))
                    return true;
            }
        }
        return false;
    }
};

440 ms 24 MB

----我的CSDN博客地址 https://michael.blog.csdn.net/

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/10/25 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法