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

AcWing——方格迷宫(有点不一样的迷宫问题)

4943. 方格迷宫 - AcWing题库

 1、题目

给定一个 n 行 m 列的方格矩阵。

行从上到下依次编号为 1∼n,列从左到右依次编号为 1∼m。

第 i 行第 j 列的方格表示为 (i,j)。

矩阵中的方格要么是空地(用 . 表示),要么是陷阱(用 # 表示)。

初始时,你位于方格 (x₁,y₁),你需要前往方格 (x₂,y₂)。

每次移动,你可以任选上、下、左、右四个方向之一,并沿该方向移动 1∼k 步。

从一个方格移动至相邻方格视为一步。

但是,你要保证在你的移动过程中不能走出矩阵,也不能进入陷阱方格。

请你计算从方格 (x₁,y₁) 移动至方格 (x₂,y₂),所需要的最少移动次数

保证方格 (x₁,y₁) 和方格 (x₂,y₂) 都是空地。

方格 (x₁,y₁) 和方格 (x₂,y₂) 可能是同一个方格。

注意:注意区分本题中移动次数与移动步数的区别。

输入格式

第一行包含三个整数 n,m,k。

接下来 n 行,每行包含 m 个字符,其中第 i 行第 j 个字符,要么是 .,表示方格 (i,j) 是空地;要么是 #,表示方格 (i,j) 是陷阱。

最后一行包含四个整数 x₁,y₁,x₂,y₂。

输出格式

一个整数,表示所需要的最少移动次数

如果无法从方格 (x₁,y₁) 移动至方格 (x₂,y₂),则输出 -1

数据范围

前 6 个测试点满足 1≤n,m≤10。
所有测试点满足 1≤n,m,k≤1000,1≤x₁,x₂≤n,1≤y₂,y₂≤m。

输入样例1:

3 4 4
....
###.
....
1 1 3 1

输出样例1:

3

输入样例2:

3 4 1
....
###.
....
1 1 3 1

输出样例2:

8

输入样例3:

2 2 1
.#
#.
1 1 2 2

输出样例3:

-1

2、题目解读

走迷宫_牛客题霸_牛客网 (nowcoder.com)

牛客网这题就是正常,普通求解最短步数的迷宫问题,而这题添加了一个条件:每次移动你可以任选上、下、左、右四个方向之一,并沿该方向移动 1∼k 步这称为 一次移动。

我们使用BFS去正常解答这道题目时间复杂度为O(nmk)最大为10⁹,这就会超时。


import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {static int n,m,k,x1,x2,y1,y2;static char[][] ch;static int[][] move ={{0,1},{0,-1},{1,0},{-1,0}};//四个方向,偏移量static int inf=0x3f3f3f3f;//初始化移动次数static int[][] ans;//记录移动次数public static void main(String[] args){Scanner sc=new Scanner(System.in);n=sc.nextInt();m=sc.nextInt();k=sc.nextInt();ch =new char[n][];ans =new int[n][m];for(int i=0;i<n;i++){ch[i]=sc.next().toCharArray();}x1=sc.nextInt()-1;y1=sc.nextInt()-1;x2=sc.nextInt()-1;y2=sc.nextInt()-1;for(int i=0;i<n;i++){//初始化移动次数Arrays.fill(ans[i],inf);}System.out.println(bfs());}public static int bfs(){ans[x1][y1]=0;Queue<int[]> q=new LinkedList<>();q.add(new int[]{x1,y1,0});while(!q.isEmpty()){int[] a =q.poll();for(int[] mo :move){//四个方向for(int i=1;i<=k;i++){//移动一次:移动1-k步int x=a[0]+mo[0]*i,y=a[1]+mo[1]*i;if(x<0||x==n||y<0||y==m||ch[x][y]=='#'){//不能出去,不能跨越陷阱break;}if(ans[x][y]>a[2]+1){//修改移动次数ans[x][y]=a[2]+1;q.add(new int[]{x,y,a[2]+1});}}}}//走完整个地图,判断目的地是否可以走到return ans[x2][y2]==inf?-1:ans[x2][y2];}
}

我们需要优化代码,看下面图:

 

所以我们应该 更新到格子发现不是最优,就应该停止。这样时间复杂度就退化到了O(nm)

需要在判断条件处新加:ans[x][y]<a[2]+1

3、代码


import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {static int n,m,k,x1,x2,y1,y2;static char[][] ch;static int[][] move ={{0,1},{0,-1},{1,0},{-1,0}};//四个方向,偏移量static int inf=0x3f3f3f3f;//初始化移动次数static int[][] ans;//记录移动次数public static void main(String[] args){Scanner sc=new Scanner(System.in);n=sc.nextInt();m=sc.nextInt();k=sc.nextInt();ch =new char[n][];ans =new int[n][m];for(int i=0;i<n;i++){ch[i]=sc.next().toCharArray();}x1=sc.nextInt()-1;y1=sc.nextInt()-1;x2=sc.nextInt()-1;y2=sc.nextInt()-1;for(int i=0;i<n;i++){//初始化移动次数Arrays.fill(ans[i],inf);}System.out.println(bfs());}public static int bfs(){ans[x1][y1]=0;Queue<int[]> q=new LinkedList<>();q.add(new int[]{x1,y1,0});while(!q.isEmpty()){int[] a =q.poll();for(int[] mo :move){//四个方向for(int i=1;i<=k;i++){//移动一次:移动1-k步int x=a[0]+mo[0]*i,y=a[1]+mo[1]*i;//不能出去,不能跨越陷阱,还有更新到格子发现不是最优,就应该停止if(x<0||x==n||y<0||y==m||ch[x][y]=='#'||ans[x][y]<a[2]+1){break;}if(ans[x][y]>a[2]+1){//修改移动次数ans[x][y]=a[2]+1;q.add(new int[]{x,y,a[2]+1});}}}}//走完整个地图,判断目的地是否可以走到return ans[x2][y2]==inf?-1:ans[x2][y2];}
}

 

相关文章:

AcWing——方格迷宫(有点不一样的迷宫问题)

4943. 方格迷宫 - AcWing题库 1、题目 给定一个 n 行 m 列的方格矩阵。 行从上到下依次编号为 1∼n&#xff0c;列从左到右依次编号为 1∼m。 第 i 行第 j 列的方格表示为 (i,j)。 矩阵中的方格要么是空地&#xff08;用 . 表示&#xff09;&#xff0c;要么是陷阱&#xf…...

《常规脉搏传输时间作为人体血压变化标志》阅读笔记

目录 一、论文摘要 二、论文十问 Q1: 论文试图解决什么问题&#xff1f; Q2: 这是否是一个新的问题&#xff1f; Q3: 这篇文章要验证一个什么科学假设&#xff1f; Q4: 有哪些相关研究&#xff1f;如何归类&#xff1f;谁是这一课题在领域内值得关注的研究员&#xff1f; …...

java学习之异常三

目录 一、throws 一、基本说明 二、使用细节 二、自定义异常 一、 基本概念 ​编辑二、自定义异常的步骤 三、实例 四、练习 三、throw和throws的区别 四、本章作业 第一道 第二题 第三题 第四题 一、throws 一、基本说明 package com.hspedu.throws_;import java.i…...

生产者向 Kafka 发送消息的执行流程

&#xff08;1&#xff09;生产者要往 Kafka 发送消息时&#xff0c;需要创建 ProducerRecoder,代码如下&#xff1a; ProducerRecord<String,String> record new ProducerRecoder<>("CostomerCountry","Precision Products","Fr…...

Linux命令·netstat

netstat命令用于显示与IP、TCP、UDP和ICMP协议相关的统计数据&#xff0c;一般用于检验本机各端口的网络连接情况。netstat是在内核中访问网络及相关信息的程序&#xff0c;它能提供TCP连接&#xff0c;TCP和UDP监听&#xff0c;进程内存管理的相关报告。 如果你的计算机有时候…...

《心安即是归处》读书笔记

目录 作者简介 经典摘录 一个人活在世界上&#xff0c;必须处理好三个关系 什么叫人生呢&#xff1f; 谈一下人性的问题 了解人生的意义与价值 人生之美 评断一本书的好与坏有什么标准呢&#xff1f; 知足知不足 作者简介 季羡林&#xff0c;随便查询一下作者简介&…...

C++:使用红黑树封装map和set

目录 一. 如何使用一颗红黑树同时实现map和set 二. 红黑树的节点插入操作 三. 红黑树迭代器的实现 3.1 begin()和end() 3.2 operator和operator-- 3.3 红黑树迭代器实现完整版代码 四. map和set的封装 附录&#xff1a;用红黑树封装map和set完整版代码 1. RBTree.h文件…...

Go 命令

目录 文章目录 go buildgo cleango fmtgo getgo installgo testgo toolgo generategodoc其它命令 go build 这个命令主要用于编译代码。在包的编译过程中&#xff0c;若有必要&#xff0c;会同时编译与之相关联的包。 如果是普通包&#xff0c;就像我们在1.2节中编写的mymath包…...

LEO、HW、LSO、LW 分别代表什么?

LEO &#xff1a;是 LogEndOffset 的简称&#xff0c;代表当前日志文件中下一条。HW&#xff1a;水位或水印一词&#xff0c;也可称为高水位 &#xff08;high watermark&#xff09; ,通常被用在流式处理领域 &#xff08;flink、spark&#xff09; &#xff0c;以表征元素…...

问题 B: 跳石头(C++)(二分答案)

目录 1.题目描述 2.AC 1.题目描述 问题 B: 跳石头 时间限制: 1.000 Sec 内存限制: 128 MB提交 状态 题目描述 一年一度的“跳石头”比赛又要开始了! 这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点…...

bugku——变量1

拿到题目后是一串PHP代码&#xff0c;给到提示是flag在变量中&#xff0c;接下来进行代码审计 error_reporting(0)&#xff1a;关闭错误报告 include “flag1.php”:包含flag1.php文件 highlight_file(_file_)&#xff1a;页面进行语法高亮显示 isset($_GET[‘args’])&#xf…...

网络数据包丢失监控

什么是网络数据包 数据包或网络数据包是通过网络传输的小数据单元。顾名思义&#xff0c;这些是小的、离散的数据单元。单独来看&#xff0c;这些单位不一定有多大意义。它们只是正在传输的整体消息的一部分&#xff0c;这些消息已被组装成多个层。但是&#xff0c;当组合在一…...

Linux服务器安装部署MongoDB数据库 - 无公网IP远程连接

目录 前言 1. 配置Mongodb源 2. 安装MongoDB 3. 局域网连接测试 4. 安装cpolar内网穿透 5. 配置公网访问地址 6. 公网远程连接 7. 固定连接公网地址 8. 使用固定地址连接 转载自Cpolar Lisa文章&#xff1a;Linux服务器安装部署MongoDB数据库 - 无公网IP远程连接「内网…...

CSS面试题:30道含答案和代码示例的练习题

什么是 CSS&#xff1f;它的作用是什么&#xff1f; CSS&#xff08;层叠样式表&#xff09;是一种用于描述网页样式的语言。它的作用是控制网页的布局、字体、颜色、背景等方面的样式。如何在 HTML 页面中引入 CSS&#xff1f; 可以使用 标签将 CSS 文件引入到 HTML 页面中。例…...

时间轮的golang实践浅析

引言 下列代码模仿一段RPC请求的执行过程&#xff0c;执行后会有哪些问题&#xff1a; RPC代码示例答案&#xff1a;因为超时控制后未阻断后续请求&#xff0c;导致并发读写产生Panic思考&#xff1a;客户端发起 HTTP 请求后&#xff0c;如果在指定时间内没有收到服务器的响应…...

Linux命令_stress 快速模拟CPU、内存、磁盘消耗

ping的安装命令&#xff1a;apt-get install -y inetutils-ping 会遇到Unable to locate package inetutils-ping问题 正确的操作是&#xff1a; ** 这时候需要敲&#xff1a;apt-get update&#xff0c;这个命令的作用是&#xff1a;同步 /etc/apt/sources.list 和 /etc/apt/…...

可视化绘图技巧100篇分析篇(二)-生存曲线(LM曲线)

目录 前言 几个高频面试题目 roc曲线和生存曲线区别 生存曲线模型 生存曲线组件讲解...

UP主发车啦!撩人仙侠文系列,谁来管管这个反派啊!

本人书龄4年&#xff0c;平时很爱看小说&#xff0c;阅遍无数经典修仙文&#xff0c;熬夜党的最爱啊&#xff01;&#xff01;&#xff01;&#xff01;我心中的仙侠top&#xff0c;都是我的心头爱。 一般我都会跟朋友说这六本五星级仙侠好文&#xff0c;如果她们不看&#xf…...

K8S使用持久化卷存储到NFS(NAS盘)

参考文章&#xff1a;K8S-v1.20中使用PVC持久卷 - 知乎 目录 1、概念&#xff1a; 1.1 基础概念 1.2 PV的配置 1.2.1 静态PV配置 1.2.2 动态PV配置 1.2.3 PVC与PV的绑定 1.2.4 PVC及PV的使用 2 部署PV及PVC 2.1 所有K8S机器都需要安装NFS程序 2.2 仅针对需要暴露文件…...

一图看懂 multidict 模块:类似于字典的键值对集合,键可以多次出现,资料整理+笔记(大全)

本文由 大侠(AhcaoZhu)原创&#xff0c;转载请声明。 链接: https://blog.csdn.net/Ahcao2008 一图看懂 multidict 模块&#xff1a;类似于字典的键值对集合&#xff0c;键可以多次出现&#xff0c;资料整理笔记&#xff08;大全&#xff09; &#x1f9ca;摘要&#x1f9ca;模…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...