当前位置: 首页 > news >正文

华为5.7机考-最小代价相遇的路径规划Java题解

题目内容

输入描述

输出描述

示例:

输入:

2
1 2
2 1

输出:

3

思路:

Dijkstra 算法实现

dijkstra(int sx, int sy, int[][] dirs) 方法:

  • 参数:起点坐标 (sx, sy) 和允许的移动方向

  • 初始化

    • dist 数组存储到每个点的最短距离,初始为 INF

    • 起点的距离初始化为该点的值 grid[sx][sy]

  • 优先队列:存储待处理的节点,按距离从小到大排序

  • 处理队列

    • 取出当前距离最小的点

    • 跳过已经处理过的点(距离大于当前存储的距离)

    • 检查所有允许方向的邻居

    • 如果找到更短路径,更新距离并加入队列

主逻辑

  • 从起点 (0,0) 和终点 (n-1,n-1) 分别执行 Dijkstra 算法

    • dirs1: 只允许向右和向下移动

    • dirs2: 只允许向左和向上移动

  • 遍历所有可能的中间点:

    • 检查当前点是否可达(距离不为 INF)

    • 检查四个方向的邻居是否可达

    • 计算路径的最大值(从起点到当前点,和从邻居到终点的最大值)

    • 更新全局最小值 ans

  1. Dijkstra 算法的变种

    • 传统 Dijkstra 用于图的最短路径,这里应用于网格

    • 允许的移动方向由参数控制,可以灵活调整

  2. 双向搜索思想

    • 从起点和终点分别搜索,提高效率

    • 在中间点汇合时计算最终结果

  3. 优先队列的使用

    • Java 的 PriorityQueue 默认是最小堆

    • 通过 Comparator.comparingLong(a -> a[0]) 确保按距离排序

  4. 边界条件处理

    • 检查坐标是否越界

    • 跳过值为 0 的障碍点

    • 处理不可达情况(距离为 INF)

import java.util.*;
import java.io.*;public class GridShortestPath {static final long INF = (long)1e18;static int n;static int[][] grid;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));n = Integer.parseInt(br.readLine());grid = new int[n][n];// 读取网格数据for (int i = 0; i < n; i++) {String[] row = br.readLine().split(" ");for (int j = 0; j < n; j++) {grid[i][j] = Integer.parseInt(row[j]);}}// 定义两个方向的移动int[][] dirs1 = {{0, 1}, {1, 0}};  // 向右和向下int[][] dirs2 = {{-1, 0}, {0, -1}}; // 向左和向上// 从起点(0,0)开始计算最短路径long[][] dist1 = dijkstra(0, 0, dirs1);// 从终点(n-1,n-1)开始计算最短路径long[][] dist2 = dijkstra(n-1, n-1, dirs2);long ans = INF;// 遍历所有可能的中间点for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0 || dist1[i][j] == INF) continue;// 检查四个方向的邻居int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};for (int[] dir : directions) {int ni = i + dir[0];int nj = j + dir[1];if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;if (grid[ni][nj] == 0 || dist2[ni][nj] == INF) continue;// 计算当前路径的最大值long currentMax = Math.max(dist1[i][j], dist2[ni][nj]);ans = Math.min(ans, currentMax);}}}System.out.println(ans == INF ? -1 : ans);}// Dijkstra算法实现static long[][] dijkstra(int sx, int sy, int[][] dirs) {long[][] dist = new long[n][n];for (int i = 0; i < n; i++) {Arrays.fill(dist[i], INF);}dist[sx][sy] = grid[sx][sy];// 优先队列,按距离排序PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));pq.add(new long[]{dist[sx][sy], sx, sy});while (!pq.isEmpty()) {long[] current = pq.poll();long d = current[0];int x = (int)current[1];int y = (int)current[2];if (d > dist[x][y]) continue;for (int[] dir : dirs) {int nx = x + dir[0];int ny = y + dir[1];if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;if (grid[nx][ny] == 0) continue;long nd = d + grid[nx][ny];if (nd < dist[nx][ny]) {dist[nx][ny] = nd;pq.add(new long[]{nd, nx, ny});}}}return dist;}
}

相关文章:

华为5.7机考-最小代价相遇的路径规划Java题解

题目内容 输入描述 输出描述 示例&#xff1a; 输入&#xff1a; 2 1 2 2 1 输出&#xff1a; 3 思路&#xff1a; Dijkstra 算法实现 dijkstra(int sx, int sy, int[][] dirs) 方法&#xff1a; 参数&#xff1a;起点坐标 (sx, sy) 和允许的移动方向 初始化&#xff1…...

element-ui分页的使用及修改样式

1.安装 npm install element-ui -S 2.在main.js中引入,这里是全部引入&#xff0c;也可以按需引入 import ElementUI from element-ui import element-ui/lib/theme-chalk/index.css Vue.use(ElementUI) 3.使用 layout"prev, pager, next, jumper" &#xff1a;jumpe…...

[Unity]-[UI]-[Image] 关于UI精灵图资源导入设置的详细解释

Unity UI Sprite UI资源导入详解图片导入项目Texture TypeTexture ShapeAdvanced Setting 高级设置 图片设置案例常见细节问题 知识点详解来源 UI资源导入详解 Unity中的UI资源有图片、矢量图、字体、预制体、图集、动画等等资源。 这其中图片是最重要以及最基础的资源组成&a…...

MLX-Audio:高效音频合成的新时代利器

MLX-Audio&#xff1a;高效音频合成的新时代利器 现代社会的快节奏生活中&#xff0c;对语音技术的需求越来越高。无论是个性化语音助手&#xff0c;还是内容创作者所需的高效音频生成工具&#xff0c;语音技术都发挥着不可或缺的作用。今天&#xff0c;我们将介绍一个创新的开…...

操作系统导论——第27章 插叙:线程API

关键问题&#xff1a;如何创建和控制线程&#xff1f; 操作系统应该提供哪些创建和控制线程的接口&#xff1f;这些接口如何设计得易用和实用&#xff1f; 一、线程创建 编写多线程程序的第一步就是创建新线程&#xff0c;因此必须存在某种线程创建接口。在 POSIX 中&#xff1…...

代采系统:定义、优势与未来趋势

一、代采系统的定义 代采系统是一种基于互联网的集中采购平台&#xff0c;它通过整合供应链资源&#xff0c;为中小企业或个人提供采购代理服务。商家可以在没有自己库存的情况下销售产品&#xff0c;当客户下单时&#xff0c;订单信息会自动或手动发送给供应商&#xff0c;由…...

后缀表达式+栈(详解)(c++)

前言 很抱歉&#xff0c;上一期没有介绍栈stack的用法&#xff0c;今天简要介绍一下&#xff0c;再讲讲后缀表达式&#xff0c;用stack栈做一些后缀表达式的练习。 栈 栈stack是c中系统给出的栈&#xff0c;有了它&#xff0c;就不用自己创建栈啦&#xff01; 头文件 栈sta…...

Kaggle图像分类竞赛实战总结详细代码解读

前言 我是跟着李沐的动手学深度学习v2视频学习深度学习的&#xff0c;光看不做假把式&#xff0c;所以在学习完第七章-现代卷积神经网络之后&#xff0c;参加了一次李沐发布的Kaggle竞赛。自己动手&#xff0c;从组织数据集开始&#xff0c;到训练&#xff0c;再到推理&#x…...

开源AI对比--dify、n8n

原文网址&#xff1a;开源AI对比--dify、n8n-CSDN博客 简介 本文介绍开源AI工作流工具的选型。 对比 项difyn8n占优者学习难度简单中等dify核心理念用LLM构建应用。“连接一切”。以工作流自动化连接各系统。平手工作模式 Chatflow&#xff1a;对话。支持用户意图识别、上下…...

【SQL系列】多表关联更新

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

软件设计师教程——第一章 计算机系统知识(下)

前言 在竞争激烈的就业市场中&#xff0c;证书是大学生求职的重要加分项。中级软件设计师证书专业性强、认可度高&#xff0c;是计算机相关专业学生考证的热门选择&#xff0c;既能检验专业知识&#xff0c;又有助于职业发展。本教程将聚焦核心重点&#xff0c;以点带面构建知…...

华为银河麒麟 V10(ARM)系统软件部署全攻略:Redis、RabbitMQ、MySQL 等集群搭建指南

一、Redis 集群部署&#xff08;主从 哨兵模式&#xff09; 1. 环境准备 系统&#xff1a;华为银河麒麟 V10&#xff08;ARM64&#xff09;节点&#xff1a;3 台服务器&#xff08;1 主 2 从 3 哨兵&#xff09; 2. 安装包下载 bash # 华为镜像站 wget https://update.c…...

World of Warcraft [CLASSIC][80][Deluyia] [Fragment of Val‘anyr]

瓦兰奈尔的碎片 [Fragment of Valanyr] 有时候下个班打个游戏&#xff0c;没想到套路也这么多&#xff0c;唉&#xff0c;何况现实生活&#xff0c;这一个片版本末期才1000G&#xff0c;30个&#xff0c;也就30000G&#xff0c;时光徽章等同月卡15000G&#xff0c;折合一下也就…...

C++:求分数序列和

【描述】 有一个分数序列 2/1,3/2,5/3,8/5,13/8,21/13,.... 求这个分数序列的前n项之和。 输入 输入有一行&#xff1a;正整数n。 输出 输出有一行&#xff1a;分数序列的和&#xff08;浮点数&#xff0c;精确到小数点后4位&#xff09;。 【样例输入】 99 【样例输出】 160.4…...

支付宝沙盒模式商家转账经常出现 响应异常: 解包错误

2025年5月9日16:27:08 php8.3 laravel11 octane swoole加速 测试时不时就出现 响应异常: 解包错误 错误信息&#xff1a; Yansongda\Artful\Exception\InvalidResponseException: 响应异常: 解包错误 in /opt/www/vendor/yansongda/artful/src/Direction/CollectionDirect…...

第04章—技术突击篇:如何根据求职意向进行快速提升与复盘

经过上一讲的内容阐述后&#xff0c;咱们定好了一个与自身最匹配的期望薪资&#xff0c;接着又该如何准备呢&#xff1f; 很多人在准备时&#xff0c;通常会选择背面试八股文&#xff0c;这种做法效率的确很高&#xff0c;毕竟能在“八股文”上出现的题&#xff0c;也绝对是面…...

数据统计的意义:钱包余额变动

钱包余额变动统计的核心意义在于通过数据可视化实现资金流动的透明化管理&#xff0c;其价值主要体现在以下五个维度&#xff1a; 一、财务健康诊断&#xff08;&#xff09; 资金流动可视化 通过期初/期末余额对比&#xff0c;可快速识别异常波动&#xff08;如连续3个月余额…...

单调栈模版型题目(3)

单调栈型题目贡献法 基本模版 这是数组a中的 首先我们要明白什么叫做贡献&#xff0c;在一个数组b{1,3,5}中&#xff0c;连续包含1的连续子数组为{1}&#xff0c;{1,3}&#xff0c;{1,3,5}&#xff0c;一共有三个&#xff0c;这三个数一共能组成6个连续子数组&#xff0c;而其…...

PostgreSQL 的 pg_advisory_lock 函数

PostgreSQL 的 pg_advisory_lock 函数 pg_advisory_lock 是 PostgreSQL 提供的一种应用级锁机制&#xff0c;它不锁定具体的数据库对象&#xff08;如表或行&#xff09;&#xff0c;而是通过数字键值来协调应用间的并发控制。 锁的基本概念 PostgreSQL 提供两种咨询锁(advi…...

NLP基础

1. 基本概念 自然语言处理&#xff08;Natural Language Processing&#xff0c;简称NLP&#xff09;是人工智能和语言学领域的一个分支&#xff0c;它涉及到计算机和人类&#xff08;自然&#xff09;语言之间的相互作用。它的主要目标是让计算机能够理解、解释和生成人类语言…...

[AI Tools] Dify 工具插件上传指南:如何将插件发布到官方市场

Dify 作为开源的 LLM 应用开发平台,不仅支持本地化插件开发,也提供了插件市场机制,让开发者能够将自己构建的插件发布并供他人使用。本文将详细介绍如何将你开发的 Dify Tools 插件上传至官方插件市场,包括 README 编写、插件打包、仓库 PR 等核心步骤。 一、准备 README 文…...

Qt读写XML文档

XML 结构与概念简介 XML&#xff08;可扩展标记语言&#xff09; 是一种用于存储和传输结构化数据的标记语言。其核心特性包括&#xff1a; 1、树状结构&#xff1a;XML 数据以层次化的树形结构组织&#xff0c;包含一个根元素&#xff08;Root Element&#xff09;&#xff…...

htmlUnit和Selenium的区别以及使用BrowserMobProxy捕获网络请求

1. Selenium&#xff1a;浏览器自动化之王 核心定位&#xff1a; 跨平台、跨语言的浏览器操控框架&#xff0c;通过驱动真实浏览器实现像素级用户行为模拟。 技术架构&#xff1a; 核心特性&#xff1a; 支持所有主流浏览器&#xff08;含移动端模拟&#xff09; 精…...

C#黑魔法:鸭子类型(Duck Typing)

C#黑魔法&#xff1a;鸭子类型(Duck Typing) 如果它走起路来像鸭子&#xff0c;叫起来像鸭子&#xff0c;那么它就是鸭子。 鸭子类型&#xff0c;主要应用于动态语言类型&#xff0c;比如JS、Python等&#xff0c;核心理念为&#xff1a;关注对象的行为&#xff08;方法或属性…...

2025 年数维杯数学建模B题完整论文代码模型

《2025 年数维杯数学建模B题完整论文代码模型》 B题完整论文 一、赛事背景与题目总览 2025 年第十届数维杯大学生数学建模挑战赛的 B 题聚焦于“马拉松经济的高质量发展思路探索”。近年来&#xff0c;我国马拉松赛事如同一颗颗璀璨的星星&#xff0c;在城市的天空中闪耀&am…...

C++23 中的 views::chunk:深入探索与应用

文章目录 一、views::chunk 的背景与动机二、views::chunk 的基本用法语法与参数示例代码 三、views::chunk 的高级用法处理不完整块与 views::drop 和 views::take 结合 四、性能分析五、应用场景1. 批量处理数据2. 分页显示3. 并行处理 六、与其他范围适配器的组合1. 与 view…...

库室指静脉人脸门禁机 LK-BM-S10C/JR

1、采用大于等于四核处理器&#xff0c;主频大于1G&#xff1b; 2、内存≥4G DDR3&#xff1b;存储≥8G 3、核心模块采用国产工业级处理芯片和嵌入式Android实时多任务系统&#xff0c;采用模块化设计,模块间通过标准接口相连&#xff1b; 4、大于等于10英寸电容屏&#xf…...

低成本自动化改造的18个技术锚点深度解析

执行摘要 本文旨在深入剖析四项关键的低成本自动化技术&#xff0c;这些技术为工业转型提供了显著的运营和经济效益。文章将提供实用且深入的指导&#xff0c;涵盖老旧设备联网、AGV车队优化、空压机系统智能能耗管控以及此类项目投资回报率&#xff08;ROI&#xff09;的严谨…...

线程中常用的方法

知识点详细说明 Java线程的核心方法集中在Thread类和Object类中,以下是新增整合后的常用方法分类解析: 1. 线程生命周期控制 方法作用注意事项start()启动新线程,JVM调用run()方法多次调用会抛出IllegalThreadStateException(线程状态不可逆)。run()线程的任务逻辑直接调…...

运维体系架构规划

运维体系架构规划是一个系统性工程&#xff0c;旨在构建高效、稳定、安全的运维体系&#xff0c;保障业务系统的持续运行。下面从规划目标、核心模块、实施步骤等方面进行详细阐述&#xff1a; 一、规划目标 高可用性&#xff1a;确保业务系统 724 小时不间断运行&#xff0c…...

C++结构体介绍

结构体的定义 在C中&#xff0c;结构体&#xff08;struct&#xff09;是一种用户定义的数据类型&#xff0c;允许将不同类型的数据组合在一起。结构体的定义使用struct关键字&#xff0c;后跟结构体名称和一对花括号{}&#xff0c;花括号内包含成员变量的声明。 struct Pers…...

RoPE长度外推:外插内插

RoPE:假定 α \alpha α是定值 其中一半位置是用cos表示的 cos ⁡ ( k α − 2 i d ) \cos(k\alpha^{-\frac{2i}{d}}) cos(kα−d2i​)(另一半是sin)(d是词嵌入维度) 当太长如何解决: 1 直接不管—外插 缺点:超过一定长度性能急剧下降。(较大时&#xff0c;对应的很多位置编码…...

牛客练习赛138-题解

牛客练习赛138-题解 https://ac.nowcoder.com/acm/contest/109081#question A-小s的签到题 题目描述 给定一个比赛榜单&#xff1a; 第一行是 n 个不同的大写字母&#xff0c;代表题号第二行是 n 个形如a/b的字符串&#xff0c;表示每道题的通过人数和提交人数 找到通过人…...

MySQL高可用方案全攻略:选型指南与AI运维实践

MySQL高可用方案全攻略:选型指南与AI运维实践 引言:当数据库成为业务生命线 在数字化时代,数据库就是企业的"心脏"。一次数据库宕机可能导致: 电商网站每秒损失上万元订单游戏公司遭遇玩家大规模流失金融系统引发连锁反应本文将为你揭秘: MySQL主流高可用方案…...

【库(Library)、包(Package)和模块(Module)解析】

在Python中&#xff0c;**库&#xff08;Library&#xff09;、包&#xff08;Package&#xff09;和模块&#xff08;Module&#xff09;**是代码组织的不同层级&#xff0c;而import语句的导入行为与它们密切相关。以下是详细对比和解释&#xff1a; &#x1f4e6; 1. 核心概…...

记录一次使用thinkphp使用PhpSpreadsheet扩展导出数据,解决身份证号码等信息科学计数法问题处理

PhpSpreadsheet官网 PhpSpreadsheet安装 composer require phpoffice/phpspreadsheet使用composer安装时一定要下载php对应的版本&#xff0c;下载之前使用php -v检查当前php版本 简单使用 <?php require vendor/autoload.php;use PhpOffice\PhpSpreadsheet\Spreadshee…...

为什么业务总是被攻击?使用游戏盾解决方案

业务频繁遭受攻击的核心原因在于攻防资源不对等&#xff0c;攻击者利用技术漏洞、利益驱动及企业防护短板发起攻击&#xff0c;而游戏盾通过针对性架构设计实现高效防御。以下是具体分析与解决方案&#xff1a; ​​一、业务被攻击的根源​​ ​​利益驱动攻击​​ ​​勒索与数…...

4.1【LLaMA-Factory 实战】医疗领域大模型:从数据到部署的全流程实践

【LLaMA-Factory实战】医疗领域大模型&#xff1a;从数据到部署的全流程实践 一、引言 在医疗AI领域&#xff0c;构建专业的疾病诊断助手需要解决数据稀缺、知识专业性强、安全合规等多重挑战。本文基于LLaMA-Factory框架&#xff0c;详细介绍如何从0到1打造一个垂直领域的医…...

二维旋转矩阵:让图形动起来的数学魔法 ✨

大家好&#xff01;今天我们要聊一个超酷的数学工具——旋转矩阵。它就像数学中的"旋转魔法"&#xff0c;能让图形在平面上优雅地转圈圈。别被"矩阵"这个词吓到&#xff0c;其实它就是一个数字表格&#xff0c;但功能超级强大&#xff01; 一、什么是旋转…...

go语言封装、继承与多态:

1.封装&#xff1a; 封装是通过将数据和操作数据的方法绑定在一起来实现的。在Go语言中&#xff0c;封装通过结构体&#xff08;struct&#xff09;和方法&#xff08;method&#xff09;来实现。结构体的字段可以通过大小写来控制访问权限。 package stutype Person struct …...

golang -- 如何获取变量类型

目录 前言获取变量类型一、fmt.Printf二、类型断言三、类型选择四、反射 reflect.TypeOf五、reflect.Value的Type()方法 前言 在学习反射的时候&#xff0c;对reflect包中获取变量类型的函数很迷惑 比如下面这个 用Type获取变量类型的方法&#xff08;在下面提到&#xff09; …...

Missashe考研日记-day36(改版说明)

Missashe考研日记-day36 改版说明 经过一天的思考、纠结和尝试&#xff0c;博主决定对更新内容进行改版&#xff0c;如下&#xff1a;1.不再每天都发一篇日记&#xff0c;改为一周发一篇包含一周七天学习进度的周记&#xff0c;但为了标题和以前相同&#xff08;强迫症&#…...

opencv中的图像特征提取

图像的特征&#xff0c;一般是指图像所表达出的该图像的特有属性&#xff0c;其实就是事物的图像特征&#xff0c;由于图像获得的多样性&#xff08;拍摄器材、角度等&#xff09;&#xff0c;事物的图像特征有时并不特别突出或与无关物体混杂在一起&#xff0c;因此图像的特征…...

一文了解氨基酸的分类、代谢和应用

氨基酸&#xff08;Amino acids&#xff09;是在分子中含有氨基和羧基的一类化合物。氨基酸是生命的基石&#xff0c;人类所有的疾病与健康状况都与氨基酸有直接或间接的关系。氨基酸失衡可引起肝硬化、神经系统感染性疾病、糖尿病、免疫性疾病、心血管疾病、肾病、肿瘤等各类疾…...

Linux 系统安装Minio详细教程

一、&#x1f50d; MinIO 简介 MinIO 是一个高性能的对象存储服务&#xff0c;兼容 Amazon S3 接口&#xff0c;适用于大数据、AI、云原生等场景&#xff0c;支持分布式部署和高可用性&#xff0c;可作为轻量级的私有云对象存储解决方案。 二、&#x1f4e6; 安装准备 ✅ 系…...

排序算法-归并排序

归并排序是一种分治算法&#xff08;Divide and Conquer&#xff09;。对于给定的一组数据&#xff0c;利用递归与分治技术将数据序列划分成为越来越小的半子表&#xff0c;在对半子表排序后&#xff0c;再用递归方法将排好序的半子表合并成为越来越大的有序序列。 核心思想 分…...

js 两个数组中的指定参数(id)相同,为某个对象设置disabled属性

在JavaScript中&#xff0c;如果想要比较两个数组并根据它们的id属性来设置某个对象的disabled属性为true&#xff0c;你可以使用几种不同的方法。这里我将介绍几种常用的方法&#xff1a; 方法1&#xff1a;使用循环和条件判断 const array1 [{ id: 1, name: Item 1 },{ id…...

【Java基础】——集合篇

目标&#xff1a; 1.每个集合用的场景 2.每个集合的底层 一.概述 二. 三.Collection 1.通用方法 其中&#xff0c;contains方法&#xff0c;它的底层一定调用了equals方法进行比对&#xff0c;而且一定重写了equals方法&#xff0c;如果不重写equals方法&#xff0c;就是调用…...

小红书视频无水印下载方法

下载小红书&#xff08;RED/Xiaohongshu&#xff09;视频并去除水印可以通过以下几种方法实现&#xff0c;但请注意尊重原创作者版权&#xff0c;下载内容仅限个人使用&#xff0c;避免侵权行为。 方法一&#xff1a;使用在线解析工具&#xff08;推荐&#xff09; 复制视频链…...

代发考试战报:思科华为HCIP HCSE CCNP 考试通过

CCNP 300-410考试通过战报&#xff0c;HCIP云计算通过&#xff0c;HCIP数通 H12-821考试通过&#xff0c;H12-831考试通过&#xff0c;HCSP金融 H19-611考试通过&#xff0c;HCSE金融 H21-293 考试通过 报名考试一定要找正规报名&#xff0c;避免后续考试成绩被取消&#xff0…...