1631. 最小体力消耗路径

一、题目

1、题目描述

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

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

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

2、接口描述

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {

    }
};

3、原题链接

1631. 最小体力消耗路径


二、解题报告

1、思路分析

显然我们是要找到左上到右下所有路径中最小的体力消耗值,我们不妨定义边权为高度差,随后我们有两种选择:

F1 按照最短路求解

在本题中,我们路径长度变为了路径上最大高度差,那么我们仍然能用最短路求解,我们以Dijkstra为例,我们dist转移从加权转移变为了最大高度差转移

F2 Kruscal

为什么能用Kruscal?当我们执行生成树流程,当加入一条边使得起点终点连通,那么这条边权就是我们的答案。

证明:设最后一条边e

1、往证e在最优路径上

如果e不在最优路径上,那么由于我们按照所有边从边权从大到小取边,e之前的边必已经令起点终点连通,那么不会进行到e的情况,因为我们已经返回答案了

2、往证e的边权是最优路径上最大的

假设前面有边权比e权值大,那么由于我们从权值从小到大取边,e必然比前面的大,又矛盾了

1、2得证

2、复杂度

Dijkstra:

时间复杂度:O(mn\log_{2}({mn}))空间复杂度:O(mn)

Kruscal:

时间复杂度:O(mn\log_{2}({mn}))空间复杂度:O(mn)

3、代码详解

​Dijkstra
class Solution {
private:
    typedef pair<int, int> PII; 
    #define N 10010
    int dir[5]{0,1,0,-1,0};
    int dist[N];
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int m = heights.size(), n = heights[0].size();
        memset(dist, 0x3f, sizeof dist);
        bitset<N> vis;
        dist[0] = 0;
        priority_queue<PII, vector<PII>, greater<>> heap;
        heap.emplace(0, 0);
        auto posxy = [&](int id){return PII{id / n, id % n};};
        auto pos = [&](int x, int y){return x * n + y;};
        while (heap.size()) {
            auto t = heap.top();
            heap.pop();
            int ver = t.second, w = t.first;
            if (vis[ver]) continue;
            vis[ver] = true;
            auto [x, y] = posxy(ver);
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i], ny = y + dir[i+1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; 
                int nver = pos(nx, ny);
                int nw = max(w,abs(heights[x][y] - heights[nx][ny]));
                if(dist[nver] > nw)
                {
                    dist[nver] = nw;
                    heap.emplace(nw, nver);
                }
                
            }
        }
        return dist[n * m - 1];
    }
};
Kruscal
class Solution {
public:
struct edge
{
    int u , v , w;
    bool operator<(const edge& e)
    {
        return w < e.w;
    }
};
int p[10001];
int findp(int x)
{
    return p[x] < 0 ? x : p[x] = findp(p[x]);
}
void Union(int x , int y)
{
    int px = findp(x) , py = findp(y);
    if(px == py) return;
    if(p[px] > p[py]) swap(px , py);
    p[px] += p[py];
    p[py] = px;
}
bool isUnion(int x , int y)
{
    return findp(x) == findp(y);
}
static constexpr int dir[]{0 , 1 , 0};
    int minimumEffortPath(vector<vector<int>>& heights) {
        memset(p , -1 , sizeof(p));
        vector<edge> edges;
        int m = heights.size() , n = heights[0].size();
        auto pos = [&](int x , int y)->int{
            return x*n+y;
        };
        for(int i = 0 ; i < m ; i++)
        {
            for(int j = 0 ; j < n ; j++)
            {
                for(int k = 0 ; k < 2 ; k++)
                {
                    int nx = i + dir[k] , ny  = j + dir[k + 1];
                    if(nx >= m || ny >= n) continue;
                    int w = abs(heights[nx][ny] - heights[i][j]);
                    edges.emplace_back(edge{pos(i,j) , pos(nx,ny) , w});
                }
            }
        }
        long long ret = 0;
        sort(edges.begin() , edges.end());
        for(auto& e : edges)
        {
            if(isUnion(e.u,e.v)) continue;
            Union(e.u,e.v);
            if(isUnion(0 , m*n-1)) return e.w;
        }
        return ret;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/235551.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

分布式事务Seata(别名Seta)(持续学习中)

1.为什么学习他? 当一台机器的时候,只需要本地事务回滚就好了,还有MonogoDB最好不要放敏感数据,特别是旧的版本,没有事务功能(ACID), 分布式事务,也是属于多线程问题,就是把多台机器变成一台机器(他拥有更多线程,但是也要考虑网络问题),redis在一台机器是单线程的,但是多台机器…

Playground v2:a new leap in creativity

https://huggingface.co/playgroundai/playground-v2-1024px-aesthetichttps://huggingface.co/playgroundai/playground-v2-1024px-aestheticPlayground v2&#xff1a;超越SDXL的模型来了 - 知乎Playground团队刚刚发布了新的文生图模型Playground v2&#xff0c;它是基于SDX…

基于MyBatis二级缓存深入装饰器模式

视频地址 学习文档 文章目录 一、示意代码二、装饰器三、经典案例—MyBatis二级缓存1、Cache 标准定义2、PerpetualCache 基础实现3、增强实现3-1、ScheduledCache3-2、LruCache 先来说说我对装饰器理解&#xff1a;当你有一个基础功能的代码&#xff0c;但你想在不改变原来代…

案例027:基于微信小程序的校园二手平台的设计与实现

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;SSM JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.5.4 小程序框架&#xff1a;uniapp 小程序开发软件&#xff1a;HBuilder X 小程序…

【Docker】进阶之路:(二)Docker简介

【Docker】进阶之路&#xff1a;&#xff08;二&#xff09;Docker简介 什么是 DockerDocker 由来与发展历程Docker的架构与组成Docker容器生态容器核心技术容器规范容器平台技术 为什么使用DockerDocker的应用场景 什么是 Docker 简单地讲&#xff0c;Docker就是一个应用容器…

面向对象类的设计和实现

实验目标 本实验任务是实现 Java 类的设计和实现&#xff0c;实验任务是根据每年新生的报到流程&#xff0c; 设计一 个学生管理系统&#xff0c;实现学生的注册和报到功能。设置类的基本属性&#xff0c;实现 getter 和 setter 方 法&#xff0c;通过 set 方法设置…

C++新经典模板与泛型编程:SFINAE特性的信息萃取

用成员函数重载实现is_default_constructible 首先介绍一个C标准库提供的可变参类模板std::is_default_constructible。这个类模板的主要功能是判断一个类的对象是否能被默认构造&#xff08;所谓默认构造&#xff0c;就是构造一个类对象时&#xff0c;不需要给该类的构造函数…

三层交换原理

三层交换机出现的背景 早期的网络中一般使用二层交换机来搭建局域网&#xff0c;而不同局域网之间的网络互通由路由器来完成。那时的网络流量&#xff0c;局域网内部的流量占了绝大部分&#xff0c;而网络间的通信访问量比较少&#xff0c;使用少量路由器已经足够应付了。 但…

六级高频词汇3

目录 单词 参考链接 单词 400. nonsense n. 胡说&#xff0c;冒失的行动 401. nuclear a. 核子的&#xff0c;核能的 402. nucleus n. 核 403. retail n. /v. /ad. 零售 404. retain vt. 保留&#xff0c;保持 405. restrict vt. 限制&#xff0c;约束 406. sponsor n. …

GRE与顺丰圆通快递盒子

1. DNS污染 随想&#xff1a; 在输入一串网址后&#xff0c;会发生如下变化如果你在系统中配置了 Hosts 文件&#xff0c;那么电脑会先查询 Hosts 文件如果 Hosts 里面没有这个别名&#xff0c;就通过域名服务器查询域名服务器回应了&#xff0c;那么你的电脑就可以根据域名服…

使用阿里巴巴同步工具DataX实现Mysql与ElasticSearch数据同步

一、Linux环境要求 二、准备工作 2.1 Linux安装jdk 2.2 linux安装python 2.3 下载DataX&#xff1a; 三、DataX压缩包导入&#xff0c;解压缩 四、编写同步Job 五、执行Job 六、定时更新 6.1 创建定时任务 6.2 提交定时任务 6.3 查看定时任务 七、增量更新思路 一、Linux环境要…

KubeSphere应用【二】Docker安装

一、Docker安装 1.下载Docker安装包 【地址】Index of linux/static/stable/x86_64/ 2.上传至服务器 # 解压文件 tar -xvf docker-20.10.10.tgz# 将docker 目录中的所有文件复制至/usr/bin/目录下 cp docker/* /usr/bin 3.配置docker.service文件 vim /usr/lib/systemd/sy…

WPF仿网易云搭建笔记(2):组件化开发

文章目录 前言专栏和Gitee仓库依赖属性实战&#xff1a;缩小&#xff0c;全屏&#xff0c;关闭按钮依赖属性操作封装主窗口传递this本身给TitleView标题控件主要代码MainWindow.xmalMainWindow.cs依赖属性方法封装TitleView.csTitleViewModelTitleViewModel实现效果 前言 这次…

【JavaWeb学习专栏 | CSS篇】css简单介绍 css常用选择器集锦

个人主页&#xff1a;[兜里有颗棉花糖(https://xiaofeizhu.blog.csdn.net/) 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【JavaWeb学习专栏】【Java系列】 希望本文内容可以帮助到大家&#xff0c;一起加油吧&#xff01;…

安全访问服务边缘(SASE):解决第三方风险的全方位解决方案

随着数字化时代的到来&#xff0c;企业和组织对于网络安全的需求越来越迫切。传统的安全解决方案已经无法满足复杂多变的网络环境&#xff0c;因此新兴的安全访问服务边缘&#xff08;SASE&#xff09;应运而生。本文将介绍SASE的概念和工作原理&#xff0c;并重点阐述它作为第…

第二百回 如何获取App自身的信息

文章目录 1. 概念介绍2. 使用方法2.1 ClipOval2.2 ClipRRect 3. 示例代码 我们在上一章回中介绍了AspectRatio Widget相关的内容&#xff0c;本章回中将介绍剪裁类组件(Clip).闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念介绍 我们在这里说的剪裁类组件主要是指对…

Koa2从零搭建restful API

Koa2从零搭建restful API: 创建项目文件夹并进入 mkdir koa-projectcd koa-project 初始化项目 npm init 安装 Koa npm install koa koa-router --save 编写示例代码&#xff0c;在 app.js 文件中编写以下代码&#xff1a; // koa项目的入口文件 const Koa require("koa…

018 OpenCV 人脸检测

目录 一、环境 二、分类器原理 2.1、概述 2.2、工作原理 三、人脸检测代码 一、环境 本文使用环境为&#xff1a; Windows10Python 3.9.17opencv-python 4.8.0.74 二、分类器原理 CascadeClassifier是OpenCV&#xff08;开源计算机视觉库&#xff09;中的一个强大的类…

想进阶JAVA高级程序员吗?多线程必学

❤️作者主页&#xff1a;小虚竹 ❤️作者简介&#xff1a;大家好,我是小虚竹。2022年度博客之星评选TOP 10&#x1f3c6;&#xff0c;Java领域优质创作者&#x1f3c6;&#xff0c;CSDN博客专家&#x1f3c6;&#xff0c;华为云享专家&#x1f3c6;&#xff0c;掘金年度人气作…

Truffle的基础语法与js测试语法

truffle编译 truffle compiletruffle部署 truffle migratetruffle测试 使用test文件夹下的所有文件测试 truffle test使用单个文件 测试 truffle test 文件所在位置assert断言 assert.equal 是一种常见的断言函数&#xff0c;用于测试两个值是否相等。它接受两个参数&…