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

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

XCTF-web-easyupload

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

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...