1631. 最小体力消耗路径

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

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

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

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

示例 1:

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:

1631. 最小体力消耗路径,算法

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

示例 3:

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

提示:

  • rows == heights.length
  • columns == heights[i].length
  • 1 <= rows, columns <= 100
  • 1 <= heights[i][j] <= 106

 

int minimumEffortPath(vector<vector<int>>& heights)
{
    int r = heights.size();
    int c = heights[0].size();
    vector<int> x{ -1,1,0,0 };
    vector<int> y{ 0,0,-1,1 };

    //最小值先出队
    auto tupleCmp = [](const auto& e1, const auto& e2) {
        return get<2>(e1) > get<2>(e2); 
    };
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, decltype(tupleCmp)> que(tupleCmp);
    que.emplace(0, 0, 0);

    vector<vector<bool>>visited(r+1, vector<bool>(c + 1, false));
    vector<int>ret(r *c+1, INT32_MAX);
    ret[0] = 0;
    while (!que.empty())
    {
        auto item = que.top();

        std::cout << get<2>(item) << std::endl;
        
        if (get<0>(item) == r - 1 && get<1>(item) == c - 1)
        {
            break;
        }
        que.pop();
        int row = get<0>(item);
        int col = get<1>(item);    
        if (visited[row][col] == true)
        {
            continue;
        }
        visited[row][col] = true;

        for (int i = 0; i < 4; i++)
        {
            if (row + x[i] < 0 || col + y[i] < 0 || row + x[i] >= heights.size()
                || col + y[i] >= heights[0].size())
            {
                continue;
            }
            
            int tmp = std::max(get<2>(item), abs(heights[row + x[i]][col + y[i]] - heights[row][col]));//保存之前最大值,get<2>(item)
            if (tmp < ret[(row + x[i])*c + col + y[i]])
            {
                ret[(row + x[i])*c + col + y[i]] = tmp;    
                que.emplace(row + x[i], col + y[i], tmp);
            }    
        }
    
    }
    return ret[r*c-1];

}文章来源地址https://www.toymoban.com/news/detail-676104.html

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

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

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

相关文章

  • 面试算法100:三角形中最小路径之和

    在一个由数字组成的三角形中,第1行有1个数字,第2行有2个数字,以此类推,第n行有n个数字。例如,下图是一个包含4行数字的三角形。如果每步只能前往下一行中相邻的数字,请计算从三角形顶部到底部的路径经过的数字之和的最小值。从三角形顶部到底部的路径数字之和

    2024年01月16日
    浏览(43)
  • 算法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日
    浏览(44)
  • 【算法|动态规划No.17】leetcode64. 最小路径和

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

    2024年02月07日
    浏览(45)
  • AcWing 379. 捉迷藏(最小路径点覆盖&&匈牙利算法)

    输入样例: 输出样例:

    2024年02月14日
    浏览(38)
  • 算法刷刷刷|动态规划篇|509.斐波那契数| 70.爬楼梯| 746.使用最小花费爬楼梯| 62.不同路径| 63不同路径2| 343.正数拆分 | 96.不同的二叉搜索树

    509. 斐波那契数 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n 1 给定 n ,请计算 F(n) 。 70.爬楼梯 746.使用最小花费爬楼梯 给你一个整数

    2023年04月23日
    浏览(56)
  • 代码随想录Day32 动态规划01 LeetCodeT509 斐波那契数列 T70 爬楼梯 T746 爬楼梯的最小消耗

    动态规划首先可以解决的问题有背包问题,打家劫舍问题,股票问题,子序列问题等,主要是将一个大的问题切分成多个重叠的子问题,所以动态规划一定是上一个状态递推过来的,有一个重要的 状态转移方程, 但是这也并不是解题的全部,我们将动态规划的题目基本分为五步来完成

    2024年02月06日
    浏览(68)
  • 算法学习——LeetCode力扣补充篇11(64. 最小路径和、48. 旋转图像 、169. 多数元素、394. 字符串解码、240. 搜索二维矩阵 II )

    64. 最小路径和 - 力扣(LeetCode) 描述 给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 示例 示例 1: 输入:grid = [[1,3,1],[1,5,1],[4,2,1]] 输出:7 解释:因为路径 1→3→1→

    2024年04月23日
    浏览(37)
  • DAG最小路径点覆盖,最小路径可重复覆盖,详解

    关于二分图:二分图及染色法判定 关于二分图最大匹配:二分图最大匹配——匈牙利算法详解 关于二分图带权最大完备匹配:二分图带权最大匹配-KM算法详解 概念 给定一张有向无环图,要求 用尽量少的不相交的简单路径 ,覆盖有向无环图的所有顶点(也就是 每个顶点恰好

    2024年01月17日
    浏览(50)
  • 动态规划|【路径问题】|931.下降路径最小和

    目录 题目 题目解析 思路 1.状态表示 2.状态转移方程 3.初始化 4.填表顺序 5.返回值 代码 931. 下降路径最小和 给你一个  n x n  的  方形  整数数组  matrix  ,请你找出并返回通过  matrix  的 下降路径   的   最小和  。 下降路径  可以从第一行中的任何元素开始,并从每一

    2024年04月13日
    浏览(42)
  • 【LeetCode】64.最小路径和

    给定一个包含非负整数的  m  x  n  网格  grid  ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明: 每次只能向下或者向右移动一步。 示例 1: 示例 2: 提示: m == grid.length n == grid[i].length 1 = m, n = 200 0 = grid[i][j] = 200 又是一道动态规划,这次也是

    2024年02月15日
    浏览(34)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包