当前位置: 首页 > 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;模…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)

Name&#xff1a;3ddown Serial&#xff1a;FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名&#xff1a;Axure 序列号&#xff1a;8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...

第22节 Node.js JXcore 打包

Node.js是一个开放源代码、跨平台的、用于服务器端和网络应用的运行环境。 JXcore是一个支持多线程的 Node.js 发行版本&#xff0c;基本不需要对你现有的代码做任何改动就可以直接线程安全地以多线程运行。 本文主要介绍JXcore的打包功能。 JXcore 安装 下载JXcore安装包&a…...

Linux 内存管理调试分析:ftrace、perf、crash 的系统化使用

Linux 内存管理调试分析&#xff1a;ftrace、perf、crash 的系统化使用 Linux 内核内存管理是构成整个内核性能和系统稳定性的基础&#xff0c;但这一子系统结构复杂&#xff0c;常常有设置失败、性能展示不良、OOM 杀进程等问题。要分析这些问题&#xff0c;需要一套工具化、…...