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

C++ 迷宫问题

描述

定义一个二维数组 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≤𝑛,𝑚≤10 2≤n,m≤10  , 输入的内容只包含 0≤𝑣𝑎𝑙≤1 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)
#include <iostream>
#include <utility>
#include <variant>
#include <vector>
using namespace std;constexpr int N = 10;int n, m;
int maze[N][N] = {0};
int vist[N][N] = {0};std::vector<std::pair<int, int>> path;
std::vector<std::pair<int, int>> temp;void dfs(int x, int y)
{if(x < 0 || x >= n || y < 0 || y >= m || maze[x][y] == 1 || vist[x][y] == 1){return;}vist[x][y] = 1;temp.emplace_back(x, y);//如果走到出口,则保存走过的路径if(x == n -1 && y == m - 1){path = temp;}//前后左右试探dfs(x, y+1); dfs(x+1,y);dfs(x-1,y);dfs(x, y-1);vist[x][y] = 0;temp.pop_back();
}int main() {cin >> n;cin >> m;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> maze[i][j];}}dfs(0,0);for(auto p : path){std::cout << "(" << p.first << "," << p.second <<")" << "\n"; }
}
// 64 位输出请用 printf("%lld")

相关文章:

C++ 迷宫问题

描述 定义一个二维数组 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表示可以走的路&#xff0c;只能横着走…...

【Linux】Linux文件系统中主要文件夹列举_作用说明

在Linux系统中&#xff0c;文件夹&#xff08;或称为目录&#xff09;的组织结构是系统功能和用户数据的重要组成部分。以下是Linux系统中一些主要文件夹的列举及其作用说明&#xff1a; / (根目录): 是Linux文件系统的起点。通常只包含其他目录&#xff0c;不建议直接在其中存…...

移植案例与原理 - HDF驱动框架-驱动配置(1)

HCS(HDF Configuration Source)是HDF驱动框架的配置描述源码&#xff0c;内容以Key-Value为主要形式。它实现了配置代码与驱动代码解耦&#xff0c;便于开发者进行配置管理。应该&#xff0c;类似Linux DTS(Device Tree Source)设备树。 HC-GEN(HDF Configuration Generator)是…...

坚持刷题|反转链表

文章目录 题目思考实现1. 迭代方式实现链表翻转2. 递归方式实现链表翻转 Hello&#xff0c;大家好&#xff0c;我是阿月。坚持刷题&#xff0c;老年痴呆追不上我&#xff0c;今天继续链表&#xff1a;反转链表 题目 LCR 024. 反转链表 思考 翻转链表是一个常见的算法问题&a…...

升级和维护老旧LabVIEW程序

在升级老旧LabVIEW程序至64位环境时&#xff0c;需要解决兼容性、性能和稳定性等问题。本文从软件升级、硬件兼容性、程序优化、故障修复等多个角度详细分析。具体包括64位迁移注意事项、修复页面跳转崩溃、解决关闭程序后残留进程的问题&#xff0c;确保程序在新环境中的平稳运…...

sqlite数据库整体迁移进mysql整个流程并解决中文异常问题

咨询【QQ】 sqlite轻量数据还行&#xff0c;随着数据量增大&#xff0c;不得不迁移进mysql 首先 电脑执行 sqlite3 db.sqlite3 .dump > dump.sql 会把整个sqlite的数据导出进 dump.sql中 紧接着我们把sqlite的sql转换成mysql的sql语句&#xff0c;因为mysql语句和 sq…...

Hadoop3:MapReduce中的Partition原理及自定义Partition

一、默认Partition分区配置 以WC案例来进行验证。 1、设置setNumReduceTasks 修改的代码 这行代码&#xff0c;确定了reduceTask的数量&#xff0c;也确定了分区逻辑 在mapper文件中&#xff0c;打上断点 计算分区的代码 这里会对每一个kv进行计算&#xff0c;然后&#…...

就因为没在大屏项目加全屏按钮,早上在地铁挨了领导一顿骂

“嗯嗯”&#xff0c;“嗯嗯”&#xff0c;“那产品也没说加呀”&#xff0c;“按F11不行吗&#xff1f;”&#xff0c;“嗯嗯”&#xff0c;“好的”。 早上在4号线上&#xff0c;我正坐在地铁里&#xff0c;边上站着的妹子&#xff0c;我看他背着双肩包&#xff0c;打着电话…...

STM32学习记录(八)————定时器输出PWM及舵机的控制

文章目录 前言一、PWM1.工作原理2.内部运作机制3. PWM工作模式4.PWM结构体及库函数 二、PWM控制舵机 前言 一个学习STM32的小白~ 有错误评论区或私信指出提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、PWM 1.工作原理 以向上计数为例&#xff0…...

Vue CLI,Vue Router,Vuex

前言 Vue CLI、Vue Router 和 Vuex 都是 Vue.js 生态系统中的重要组成部分&#xff0c;它们在构建 Vue 应用程序时扮演着关键角色。 Vue CLI Vue CLI 介绍 Vue CLI 是 Vue.js 的官方命令行工具&#xff0c;用于快速搭建 Vue.js 项目。它提供了一个图形界面&#xff08;通过…...

互联网广告相关概念

互联网广告概念涉及多个关键指标和定价模式&#xff0c;它们帮助广告主和广告平台衡量广告效果、优化广告投放策略&#xff0c;并计算广告成本。以下是互联网广告中一些核心概念的简要概述&#xff1a; 1.ROI (投资回报率) 衡量广告投资的效益&#xff0c;计算公式为&#xff…...

如何在服务器上部署一个java程序

如何在服务器上部署一个java程序&#xff1f; 一、在服务器上安装jdk环境 1.创建目录用于存放jdk文件 cd /usr/local 2.下载最新版oracle jdk22 wget https://download.oracle.com/java/22/latest/jdk-22_linux-x64_bin.tar.gz 3.解压 tar -zxf jdk-22_linux-x64_bin.ta…...

白酒:中国的酒文化的传承与发扬

中国&#xff0c;一个拥有五千年文明史的国度&#xff0c;其深厚的文化底蕴孕育出了丰富多彩的酒文化。在这片广袤的土地上&#xff0c;酒不仅仅是一种产品&#xff0c;更是一种情感的寄托&#xff0c;一种文化的传承。云仓酒庄的豪迈白酒&#xff0c;正是这一文化脉络中的一颗…...

算法金 | 再见!!!梯度下降(多图)

大侠幸会&#xff0c;在下全网同名「算法金」 0 基础转 AI 上岸&#xff0c;多个算法赛 Top 「日更万日&#xff0c;让更多人享受智能乐趣」 接前天 李沐&#xff1a;用随机梯度下降来优化人生&#xff01; 今天把达叔 6 脉神剑给佩奇了&#xff0c;上 吴恩达&#xff1a;机器…...

python Django安装及怎么检测是否安装成功

一、winr 输入cmd 进入控制台。输入pip install Django5.0.1 二、如果安装过程没有问题。就进行下一步进行检查是否成功安装。 三、 1.在控制台输入python&#xff0c;进入python环境 2.输入 import django 3.继续输入 django.get_version()。显示版本号表示成功安装。...

Swift开发——存储属性与计算属性

Swift语言开发者建议程序设计者多用结构体开发应用程序。在Swift语言中,结构体具有了很多类的特性(除类的与继承相关的特性外),具有属性和方法,且为值类型。所谓的属性是指结构体中的变量或常量,所谓的方法是指结构体中的函数。在结构体中使用属性和方法是因为:①匹别于结…...

如何解决input输入时存在浏览器缓存问题?

浏览器有时会在你输入表单过后缓存你的输入&#xff0c;有时候能提供方便。 但是在某些新建或新页面情况下出现历史的输入信息&#xff0c;用户体验很差。 解决方案 设置 autocomplete关闭 &#xff1a;<input type"text" autocomplete"off">增加…...

Java基础学习-方法

目录 方法基础概念 方法的格式&#xff1a; 案例&#xff1a;最简单方法的定义 案例&#xff1a;带参数的方法调用 案例&#xff1a;求圆的面积 带有返回值的方法&#xff1a; 方法注意点 方法的重载&#xff1a; ​编辑 案例&#xff1a;数组的遍历&#xff1a; 案例…...

Ribbon与Nginx的区别

负载均衡实现的位置不同&#xff1a; Ribbon&#xff1a;负载均衡器位于客户端&#xff0c;不需要单独搭建。Nginx&#xff1a;需要建立一个独立负载均衡服务器&#xff0c;服务端。 负载均衡策略&#xff1a; Ribbon&#xff1a;提供了多种负载均衡策略&#xff0c;如随机策…...

R包开发详细教程

开发一个R包可以帮助你组织和共享代码。以下是一个详细的步骤教程&#xff0c;介绍如何开发一个R包。 步骤 1: 准备工作 确保你已经安装了以下R包&#xff1a; install.packages("devtools") install.packages("roxygen2") install.packages("test…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...