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

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...