Leetcode.1631 最小体力消耗路径

这篇具有很好参考价值的文章主要介绍了Leetcode.1631 最小体力消耗路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目链接

Leetcode.1631 最小体力消耗路径 Rating : 1948

题目描述

你准备参加一场远足活动。给你一个二维 rows x columns的地图 heights,其中 heights[row][col]表示格子 ( r o w , c o l ) (row, col) (row,col) 的高度。一开始你在最左上角的格子 ( 0 , 0 ) (0, 0) (0,0) ,且你希望去最右下角的格子 ( r o w s − 1 , c o l u m n s − 1 ) (rows-1, columns-1) (rows1,columns1) (注意下标从 0 开始编号)。你每次可以往 上,下,左,右 四个方向之一移动,你想要找到耗费 体力 最小的一条路径。

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

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

示例 1:

Leetcode.1631 最小体力消耗路径

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

示例 2:

Leetcode.1631 最小体力消耗路径

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

示例 3:

Leetcode.1631 最小体力消耗路径

输入: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
解释:上图所示路径不需要消耗任何体力。

提示:
  • r o w s = = h e i g h t s . l e n g t h rows == heights.length rows==heights.length
  • c o l u m n s = = h e i g h t s [ i ] . l e n g t h columns == heights[i].length columns==heights[i].length
  • 1 < = r o w s , c o l u m n s < = 100 1 <= rows, columns <= 100 1<=rows,columns<=100
  • 1 < = h e i g h t s [ i ] [ j ] < = 1 0 6 1 <= heights[i][j] <= 10^6 1<=heights[i][j]<=106

解法:二分 + bfs

将原问题抽象为:

  • 将每个格子抽象成图中的一个点;

  • 将每两个相邻的格子之间连接一条边,长度为这两个格子本身 权值的差的绝对值

  • 原问题转化为求 左上角 到 右下角的最短路径(路径长度为整条路径上的最大的那个权值

我们可以 二分 边的权值 m i d mid mid ,即 ≤ m i d \leq mid mid 的边才将其联通。最后我们判断从起点 ( 0 , 0 ) (0,0) (0,0) 能否到 终点 ( m − 1 , n − 1 ) (m-1,n-1) (m1,n1)即可。

时间复杂度: O ( m n ∗ l o g r ) O(mn * logr) O(mnlogr)

C++代码:文章来源地址https://www.toymoban.com/news/detail-413366.html


using PII = pair<int,int>;

class Solution {
    static constexpr int dir[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};
public:
    int minimumEffortPath(vector<vector<int>>& g) {
        int m = g.size() , n = g[0].size();

        int l = 0 , r = 1e6;
        
        while(l < r){
            int mid = (l + r) >> 1;

            //判断位置是否被方问过了
            vector<bool> st(m * n);
            
            queue<PII> q;
            //起点入队
            q.emplace(0,0);
            st[0] = true;

            while(!q.empty()){
                auto [x,y] = q.front();
                q.pop();

                for(int i = 0;i < 4;i++){
                    int dx = x + dir[i][0] , dy = y + dir[i][1];
                    if(dx < 0 || dx >= m || dy < 0 || dy >= n) continue;
                    if(st[dx * n + dy] || abs(g[x][y] - g[dx][dy]) > mid) continue;
                    st[dx * n + dy] = true;
                    q.emplace(dx,dy);
                }
            }

            if(st[m * n - 1]) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

到了这里,关于Leetcode.1631 最小体力消耗路径的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法leetcode|64. 最小路径和(rust重拳出击)

    给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明 :每次只能向下或者向右移动一步。 m == grid.length n == grid[i].length 1 = m, n = 200 0 = grid[i][j] = 200 面对这道算法题目,二当家的再次陷入了沉思。 这道题和62. 不同

    2024年02月15日
    浏览(47)
  • 【算法|动态规划No.17】leetcode64. 最小路径和

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月07日
    浏览(49)
  • 2023-07-13 LeetCode每日一题(下降路径最小和)

    点击跳转到题目位置 给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的 下降路径 的 最小和 。 下降路径 可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左

    2024年02月15日
    浏览(80)
  • 【LeetCode:64. 最小路径和 | 暴力递归=>记忆化搜索=>动态规划 】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2024年02月05日
    浏览(45)
  • 2023-08-10LeetCode每日一题(下降路径最小和 II)

    点击跳转到题目位置 给你一个 n x n 整数矩阵 grid ,请你返回 非零偏移下降路径 数字和的最小值。 非零偏移下降路径 定义为:从 grid 数组中的每一行选择一个数字,且按顺序选出来的数字中,相邻数字不在原数组的同一列。 示例 1: 示例 2: 提示: n == grid.length == grid[i].

    2024年02月13日
    浏览(46)
  • Leetcode每日一题:931. 下降路径最小和(2023.7.13 C++)

    目录 931. 下降路径最小和 题目描述: 实现代码与解析: 动态规划 原理思路:         给你一个  n x n  的  方形  整数数组  matrix  ,请你找出并返回通过  matrix  的 下降路径   的   最小和  。 下降路径  可以从第一行中的任何元素开始,并从每一行中选择一个元素

    2024年02月16日
    浏览(50)
  • 动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本

    动态规划汇总 多源最短路径 字典树 视频算法专题 给你两个下标从 0 开始的字符串 source 和 target ,它们的长度均为 n 并且由 小写 英文字母组成。 另给你两个下标从 0 开始的字符串数组 original 和 changed ,以及一个整数数组 cost ,其中 cost[i] 代表将字符串 original[i] 更改为字符

    2024年02月04日
    浏览(54)
  • 【LeetCode题目详解】 977.有序数组的平方 209.长度最小的子数组59.螺旋矩阵II day2

    看完这个题目第一想法就是直接暴力解决,直接将全部平方然后进行排序。比如快排。 代码如下: 时间复杂度是 O(nlogn)或者说【O(n + nlogn)】,括号里面这个是为了比较接下来的方法。 然后看了代码随想录的视频学习了用双指针来写这道题的方法(说实话不看视频真没想到可

    2024年02月13日
    浏览(43)
  • Leetcode每日一题:1289. 下降路径最小和 II(2023.8.10 C++)

    目录 1289. 下降路径最小和 II 题目描述: 实现代码与解析: 动态规划 原理思路:         给你一个  n x n  整数矩阵  grid  ,请你返回  非零偏移下降路径  数字和的最小值。 非零偏移下降路径  定义为:从  grid  数组中的每一行选择一个数字,且按顺序选出来的数字

    2024年02月13日
    浏览(40)
  • 【LeetCode题目详解】第九章 动态规划part01 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯 (day38补)

    斐波那契数  (通常用  F(n) 表示)形成的序列称为 斐波那契数列 。该数列由  0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: 给定  n ,请计算 F(n) 。 示例 1: 示例 2: 示例 3: 提示: 0 = n = 30 斐波那契数列大家应该非常熟悉不过了,非常适合作为动规第

    2024年02月07日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包