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

华为机试 HJ43 迷宫问题

经典迷宫问题dfs
题目链接
描述
定义一个二维数组 N*M ,如 5 × 5 数组下所示:

int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};

它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。

数据范围: 2≤n,m≤10 , 输入的内容只包含 0≤val≤1

输入描述:
输入两个整数,分别表示二维数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的路。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。

输出描述:
左上角到右下角的最短路径,格式如样例所示。

示例1
输入:
5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出:
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

示例2
输入:
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0

输出:
(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)

说明:
注意:不能斜着走!!

solution:经典深搜问题

#include <iostream>
#include <vector>
using namespace std;int maze[10][10], n, m;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
vector<pair<int, int> > path;
void dfs(int x, int y){if (x < 0 || y < 0 || x >= n || y >= m || maze[x][y] != 0)return;if (x == n - 1 && y == m - 1) {maze[x][y] = 2;path.push_back(make_pair(x, y));for (int i = 0; i < path.size(); ++i) {cout << '(' << path[i].first << ',' << path[i].second << ')' << endl;}return ;}for (int i = 0; i < 4; ++i){maze[x][y] = 2;path.push_back(make_pair(x, y));dfs(x + dx[i], y + dy[i]);path.pop_back();maze[x][y] = 0;}
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i){for (int j = 0; j < m; ++j) {cin >> maze[i][j];}}dfs(0, 0);
}
// 64 位输出请用 printf("%lld")

相关文章:

华为机试 HJ43 迷宫问题

经典迷宫问题dfs 题目链接 描述 定义一个二维数组 N*M &#xff0c;如 5 5 数组下所示&#xff1a; int maze[5][5] { 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫&#xff0c;其中的1表示墙壁&#xff0c;0表示可以走…...

数据结构|链表

概念&#xff1a;链表是一种物理存储结构上非连续、非顺序的存储结构&#xff0c;数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。单链表的形式就像一条铁链环环相扣它与顺序表最大的不同是&#xff0c;单链表的数据存储是在不连续的空间&#xff0c;存储的数据里面含有…...

计算机写论文时,怎么引用文献? - 易智编译EaseEditing

首先需要清楚哪些引用必须注明[1]&#xff1a; 任何直接引用都要用引号并注明来源&#xff1b; 任何不是自己的口头或书面的观点、解释和结论都应注明来源&#xff1b; 即使不用原话&#xff0c;但是他人的思路、概念或观点也应注明&#xff1b; 不要为了适合你的观点修改原…...

实验三:贪心

1.减肥的小k1 题目描述 小K没事干&#xff0c;他要搬砖头&#xff0c;为了达到较好的减肥效果&#xff0c;教练规定的方式很特别&#xff1a; 每一次&#xff0c;小K可以把两堆砖头合并到一起&#xff0c;消耗的体力等于两堆砖头的重量之和。 经过 n-1次合并后&#xff0c; …...

MySQL日志文件

文章目录1.MySQL中的日志文件2.bin log的作用3.redo log的作用4.bin log和redo log的区别&#xff08;1&#xff09;存储的内容&#xff08;2&#xff09;功能&#xff08;3&#xff09;写入时间&#xff08;4&#xff09;写入方式5.两阶段提交6.undo log的作用1.MySQL中的日志…...

Intel8086处理器使用NASM汇编语言实现操作系统08-关于负数的相关处理idiv/cbw/cwde/cdqu/cwd/cdq/cdo/

很多人都知道一个有符号的数&#xff0c;最高位是1&#xff0c;则表示负数&#xff0c;最高位是0&#xff0c;则表示正数&#xff0c;如果假设我的CPU是4位CPU&#xff0c;那么对于1001这个数&#xff0c;是表示9&#xff0c;还是表示-7呢&#xff1f;&#xff1f;&#xff1f;…...

JavaScript 混淆技术

根据JShaman&#xff08;JShaman是专业的JavaScript代码混淆加密网站&#xff09;提供的消息&#xff0c;JavaScript混淆技术大体有以下几种&#xff1a; 变量混淆 将带有JS代码的变量名、方法名、常量名随机变为无意义的类乱码字符串&#xff0c;降低代码可读性&#xff0c;如…...

安装库报错:No CUDA runtime is found, using CUDA_HOME=‘/usr/local/cuda-11.3‘

1、报错内容 安装库时报错&#xff1a; No CUDA runtime is found, using CUDA_HOME/usr/local/cuda-11.32、检查 查看cuda版本和pytorch版本 python 进入python环境 import torch torch.__version__ torch.cuda.is_available()nvidia-smi 因此发现是由于该虚拟环境中CUDA与…...

CVTE前端面经(2023)

CVTE前端面经项目介绍&#xff08;重点&#xff09;在数据B中找到数组A对应的值&#xff0c;并把数组B对应的值放在数据最前面css1 定位2 外边距3 css高级应用3.1. 过渡3.2. 变形2. 浮动2.1 浮动元素特点2. 2 清除浮动3. html5语义标签4. 实现圣杯布局的两种方式4.1 定位浮动4.…...

基于EB工具的TC3xx_MCAL配置开发02_ICU模块配置

目录 1.概述2. ICU 硬件通道属性确认3. ICU通道配置3.1 添加一个Chanel3.2 IcuChannel->General配置3.3 IcuSignalMeasurement配置3.4 GtmTimerInputConfiguration配置3.5 MCU中的关联配置3.5.1 分配TIM资源给ICU使用3.5.2 设置TIM通道时钟分频系数1.概述 本篇开始我们基于…...

jmeter高阶系列--beanshell返回值中提取参数

1 准备环境 jmeter版本&#xff1a; ** &#xff0c;JDK&#xff1a;1.8将json.jar包置于…\apache-jmeter-5.1\lib\下&#xff1b;否则会报&#xff1a;Typed variable declaration : Class: JSONObject not found in namespace的错误&#xff1b;处理器&#xff1a;Beanshel…...

面向对象

面向对象面向对象一、什么是对象二、什么是面向对象三、对象四、什么是类五、实例变量六、实例方法七、方法重载(overload)八、构造方法九、对象的创建过程十、构造方法重载十一、this关键字面向对象 一、什么是对象 万物皆对象。 二、什么是面向对象 面向对象是一种编程思想。…...

mpi4py 运行过程中出现Read -1, expected xxx, errno = 1 解决方案

目录 问题描述 代码1&#xff08;串行&#xff09; 代码2&#xff08;并行&#xff09; 代码2执行时所用指令 错误信息 解决方案 解决方案1 解决方案2 问题描述 今天正在学习使用mpi4py&#xff0c;在对比运行以下2个代码时疯狂报错&#xff1a; 代码1&#xff08;串…...

PMP考前冲刺3.07 | 2023新征程,一举拿证

题目1-2&#xff1a;1.某公司启动了一个新型智能家电研发敏捷项目&#xff0c;组织上聘请了一位敏捷管理专业人士。在项目执行过程中&#xff0c;敏捷团队反馈用户故事包含的信息不足&#xff0c;无法理解需求&#xff0c;敏捷管理专业人应该怎么做&#xff1f;A.教导产品负责人…...

60条Python日常工作中的高频写法,收藏

一、 数字 1 求绝对值 绝对值或复数的模 In [1]: abs(-6) Out[1]: 62 进制转化 十进制转换为二进制&#xff1a; In [2]: bin(10) Out[2]: 0b1010十进制转换为八进制&#xff1a; In [3]: oct(9) Out[3]: 0o11十进制转换为十六进制&#xff1a; In [4]: hex(15) Out[4]:…...

(小甲鱼python)函数笔记合集七 函数(XI)总结 python函数的函数文档、类型注释、内省详解

一、基础复习 函数的基本用法 创建和调用函数 函数的形参与实参等等函数的几种参数 位置参数、关键字参数、默认参数等函数的收集参数*args **args 解包参数详解函数中参数的作用域 局部作用域 全局作用域 global语句 嵌套函数 nonlocal语句等详解函数的闭包&#xff08;工厂函…...

Leetcode是什么

力扣&#xff08;LeetCode&#xff09;是领扣网络旗下专注于程序员技术成长和企业技术人才服务的品牌。源自美国硅谷&#xff0c;力扣为全球程序员提供了专业的IT 技术职业化提升平台&#xff0c;有效帮助程序员实现快速进步和长期成长。 此外&#xff0c;力扣&#xff08;Leet…...

2023-03-07 MySQL—基于规则优化-子查询优化

简介 在使用MySQL编写查询语句时,有时候无法避免的会写出一些执行起来十分耗时、耗性能的语句,但是MySQL在执行这些语句的时候,还是会竭尽全力的做出一些优化,把这个很糟糕的语句转换成某种可以比较高效执行的形式,这个过程也可以被称作查询重写 条件化简 我们编写查询…...

Rocketmq技术详解

Rocketmq技术详解 运维部署 docker-compose.yml version: 3.5 services:rmqnamesrv:image: foxiswho/rocketmq:servercontainer_name: rmqnamesrvports:- 9876:9876volumes:- ./logs:/opt/logs- ./store:/opt/storenetworks:rmq:aliases:- rmqnamesrvrmqbroker:image: foxisw…...

TeeChart VCL/FMX v2023 crack

TeeChart VCL/FMX v2023 crack TeeChart Pro VCL允许您为所有领域(包括商业、工程、金融、统计、科学、医疗、实时和网络)创建通用和专用图表和绘图应用程序。TeeChart Pro VCL具有多种图表类型的图表库&#xff0c;包括2D或3D线条、条形图、水平条、区域、点、饼图、箭头、气泡…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...