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

经典算法----迷宫问题(找出所有路径)

目录

前言

问题描述

算法思路

定义方向

 回溯算法

代码实现


前言

        前面我发布了一篇关于迷宫问题的解决方法,是通过栈的方式来解决这个问题的(链接:经典算法-----迷宫问题(栈的应用)-CSDN博客),但是这个方法只可以找到一条路径,那么今天我们就进一步去讲解迷宫问题,通过回溯算法来找到全部的路径,下面就一起来看看吧!

问题描述

           给定一个迷宫,指明起点和终点,找出从起点出发到终点的有效可行路径,就是迷宫问题(maze problem)。迷宫可以以二维数组来存储表示。0表示通路,1表示障碍。注意这里规定移动可以从上、下、左、右四方方向移动,求走出迷宫的全部路径

#define m 4
#define n 4int maze[m + 2][n + 2] = {{1, 1, 1, 1, 1, 1},{1, 0, 0, 0, 1, 1},{1, 0, 1, 0, 0, 1},{1, 0, 0, 0, 1 ,1},{1, 1, 0, 0, 0, 1},{1, 1, 1, 1, 1, 1}};

 

算法思路

定义方向

同样的,每走到一个位置就要想该往哪一个方向去走,所以有东南西北这4个方向,每次往一个方向走之后就标记好当前方向和当前位置,然后同样的去进行分享的试探,当走到没路走的时候就进行原路返回。方向的定义如下:

//试探方向存储结构
typedef struct {int xx, yy;
}Direction;
//东南西北
Direction dire[4] = { {0,1},{1,0},{0,-1},{-1,0} };

 回溯算法

        回溯,计算机算法,回溯法也称试探法,它的基本思想是:从问题的某一种状态(初始状态)出发,搜索从这种状态出发所能达到的所有“状态”,当一条路走到“尽头”的时候(不能再前进),再后退一步或若干步,从另一种可能“状态”出发,继续搜索,直到所有的“路径”(状态)都试探过。这种不断“前进”、不断“回溯”寻找解的方法,就称作“回溯法”。递归回溯:由于回溯法是对解空间的深度优先搜索,找到结果或者没找到结果就原路返回去找下一条路。可以看出回溯算法是一种暴力算法,就是彻彻底底的一个一个找,找得到就走,找不到就回去。

对于本期的迷宫问题,我们要想找到全部的路径,就最好去用回溯算法,也就是一个一个找,毕竟实际情况走迷宫也是如此,在不知道的情况下,也只能去一个一个找。对于本题,我们可以这样子走,每走一个地方就把这个地方标记为-1,表示已经走过,当遇到死路的时候,就返回上一个位置,然后换一个方向来走,直到换到可以走得通的方向,走完这条路的话(当前走完的路所有坐标都标记为-1),我们就一直回溯换方向到其他方向能走的位置,直到整个地图全部能走的路都标记为-1,就结束回溯递归。

代码实现

#include<stdio.h>
#define m 4
#define n 4//试探方向存储结构
typedef struct {int xx, yy;
}Direction;
//东南西北
Direction dire[4] = { {0,1},{1,0},{0,-1},{-1,0} };typedef struct node {int x, y;
}Node;
typedef struct path {Node data[100];//标记路径位置的数组int count;//统计节点
}Path;//输出路径
void print(Path p, int* N) {*N += 1;printf("第%d条路径:\n", *N);for (int i = 0; i < p.count; i++) {printf("(%d,%d)->", p.data[i].x, p.data[i].y);}printf("Printover!\n\n");
}void find_path(int maze[][n+2], int* N, int x, int y, int endx, int endy, Path p) {//如果走到终点的时候if (x == endx && y == endy) {maze[x][y] = -1;//把终点位置存入到路径去p.data[p.count].x = x;p.data[p.count].y = y;p.count++;print(p, N);//输出路径//走完了就回到上一个位置,然后换方向走return;}else {//如果当前位置为0,也就是能走的话if (maze[x][y] == 0) {int di = 0;while (di < 4) {//4个方向都进行试探//储存当前位置p.data[p.count].x = x;p.data[p.count].y = y;p.count++;//标记为-1,表示已经走过maze[x][y] = -1;int i, j;//改变方向i = x + dire[di].xx;j = y + dire[di].yy;find_path(maze, N, i, j, endx, endy, p);//递归进入到下一个位置//回溯:回到上一个位置继续操作//当前位置给抹除掉p.count--;maze[x][y] = 0;di++;//改变方向}}//不能走的话就返回,回到上一个位置elsereturn;}
}int main() {int maze[m + 2][n + 2] = {{1, 1, 1, 1, 1, 1},{1, 0, 0, 0, 1, 1},{1, 0, 1, 0, 0, 1},{1, 0, 0, 0, 1 ,1},{1, 1, 0, 0, 0, 1},{1, 1, 1, 1, 1, 1}};Path mp;mp.count = 0;int N = 0;find_path(maze, &N, 1, 1, m, n, mp);
}

结果如下:

 以上就是本期的全部内容了,我们下次见!

分享一张壁纸: 

相关文章:

经典算法----迷宫问题(找出所有路径)

目录 前言 问题描述 算法思路 定义方向 回溯算法 代码实现 前言 前面我发布了一篇关于迷宫问题的解决方法&#xff0c;是通过栈的方式来解决这个问题的&#xff08;链接&#xff1a;经典算法-----迷宫问题&#xff08;栈的应用&#xff09;-CSDN博客&#xff09;&#xff…...

macOS下 /etc/hosts 文件权限问题修复方案

文章目录 前言解决方案权限验证 macOS下 etc/hosts 文件权限问题修复 前言 当在 macOS 上使用 vi编辑 /etc/hosts 文件时发现出现 Permission Denied 的提示,就算在前面加上 sudo 也照样出现一样的提示,解决方案如下; 解决方案 可以尝试使用如下命令尝试解除锁定; sudo chf…...

【星海出品】ansible入门(二) playbook

核心是管理配置进行批量节点部署。 执行其中的一些列tasks。 playbook由YAML语言编写。 YAML的格式如下&#xff1a; 文件名应该以 .yml 结尾 1.文件的第一行应该以“—”&#xff08;三个连字符&#xff09;开始&#xff0c;表明YAML文件的开始。 2.在同一行中&#xff0c;#之…...

Spring Boot对账号密码进行加密储存

未来避免明文硬编码&#xff0c;我们需要对密码进行加密保存&#xff0c;例如账号密码 方法 在Spring Boot中&#xff0c;可以使用Jasypt&#xff08;Java Simplified Encryption&#xff09;库来对敏感信息进行加密和解密。Jasypt提供了一种简单的方式来在应用程序中使用加密…...

总结js中常见的层次选择器

js中的层次选择器可以用于选择和操作DOM树中的元素&#xff0c;根据元素的层级关系进行选择。以下是js中常见的层次选择器&#xff1a; 1. getElementById&#xff1a;使用元素的ID属性进行选择。通过给元素设置唯一的ID属性&#xff0c;可以使用getElementById方法选择该元素…...

阿里云ECS服务器上启动的portainer无法访问的问题

如下图&#xff0c;在阿里云ECS服务器上安装并启动了portainer&#xff0c;但是在自己电脑上访问不了远程的portainer。 最后发现是要在网络安全组里开放9000端口号&#xff0c;具体操作如下&#xff1a; 在云服务器管理控制台点击左侧菜单中的网络与安全-安全组&#xff0c;然…...

JavaScript系列从入门到精通系列第十八篇:JavaScript中的函数作用域

文章目录 前言 一&#xff1a;函数作用域 前言 我们刚才提到了&#xff0c;在<Script>标签当中进行定义的变量、对象、函数对象都属于全局作用域&#xff0c;全局作用域在页面打开的时候生效在页面关闭的时候失效。 一&#xff1a;函数作用域 调用函数时创建函数作用域…...

开环模块化多电平换流器仿真(MMC)N=6(Simulink仿真)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

[C]嵌入式中变量存储方案

#include<stdio.h>#define uint8_t unsigned char #define uint16_t unsigned short #define uint24_t unsigned int #define uint32_t unsigned int #define uint64_t unsigned long long//用户自定义变量名字&#xff0c;用于存储 typedef enum {first_run 0,//…...

热迁移中VirtIO-PCI设备的配置空间处理

文章目录 问题现象定位过程日志分析源端目的端 原理分析基本原理上下文分析复现分析patch分析 总结解决方案 问题现象 集群升级虚拟化组件版本&#xff0c;升级前存量运行并挂载了virtio磁盘的虚拟机集群内热迁移到升级后的节点失败&#xff0c;QEMU报错如下&#xff1a; 202…...

模拟滤波器的基础知识和设计

信号处理工作中滤波器的应用是非常广泛的&#xff0c;可以分成模拟滤波器和数字滤波器两种&#xff0c;数字滤波器主要包括两种&#xff0c;IIR和FIR&#xff0c;这两种滤波器后面统一说&#xff0c;今天先来说一说模拟滤波器&#xff08;主要是我先用Python实现了Matlab书里面…...

机器学习基础-Pandas学习笔记

Pandas Python的数据分析库&#xff0c;与Numpy配合使用&#xff0c;可以从常见的格式如CSV、JSON等中读取数据。可以进行数据清洗、数据加工工作。数据结构Series&#xff0c;Pandas.Series(data,index,dtype,name,copy) data类型是Numpy的ndarray类型&#xff0c;index指定下…...

【GIT版本控制】--协作流程

一、Fork与Pull Request Git协作流程中的关键概念包括Fork和Pull Request&#xff0c;它们允许多人在项目中协作并贡献代码。以下是关于Fork和Pull Request的简要总结&#xff1a; 1. Fork&#xff1a; Fork是指复制一个Git仓库&#xff0c;通常是一个开源项目的仓库&#xf…...

简析Cookie、Session、Token

手打不易&#xff0c;如果转摘&#xff0c;请注明出处&#xff01; 注明原文&#xff1a;https://zhangxiaofan.blog.csdn.net/article/details/133498756 文章目录 简析Cookie、Session、Token什么是 Cookie &#xff1f;什么是 Session &#xff1f;Cookie 和 Session 到底是…...

加速attention计算的工业标准:flash attention 1和2算法的原理及实现

transformers目前大火&#xff0c;但是对于长序列来说&#xff0c;计算很慢&#xff0c;而且很耗费显存。对于transformer中的self attention计算来说&#xff0c;在时间复杂度上&#xff0c;对于每个位置&#xff0c;模型需要计算它与所有其他位置的相关性&#xff0c;这样的计…...

小程序获取用户手机号

在小程序中获取用户手机号需要以下步骤&#xff1a; 首先需要授权用户手机号&#xff0c;即在小程序中调用 wx.login() 方法获取用户的登录凭证&#xff0c;在回调函数中调用 wx.getUserInfo() 方法获取用户的个人信息&#xff0c;并且设置 withCredentials 参数为 true。 在获…...

Zama的fhEVM:基于全同态加密实现的隐私智能合约

1. 引言 Zama的fhEVM定位为&#xff1a; 基于全同态加密实现的隐私智能合约 解决方案 开源代码见&#xff1a; https://github.com/zama-ai/fhevm&#xff08;TypeScript Solidity&#xff09; Zama的fhEVM协议中主要包含&#xff1a; https://github.com/zama-ai/tfhe-…...

Mac M1安装ROS1或ROS2

1.首先进入Anaconda官网&#xff0c;安装Anaconda 2.创建、激活并配置环境 #创建环境 conda create -n ROS #激活环境 conda activate ROS #配置环境 conda config --add channels conda-forge conda config --add channels robostack conda config --set channel_priority st…...

[NISACTF 2022]popchains - 反序列化+伪协议

[NISACTF 2022]popchains 一、解题流程二、小小疑惑 一、解题流程 1、链条&#xff1a;Road_is_Long&#xff08;construct->wakeup【page$r】-> toString【string$m】&#xff09;-> Make_a_Change&#xff08;construct->get【effort$t】&#xff09;-> Try_W…...

分贝定义简介

一、什么是分贝 辅助单元Bel表示任何给定部件、电路或系统的输入和输出之间的对数比L,并且可以用电压、电流或功率来表示: 如果使用场量(电压或电流)代替功率量,则: 我们可以将增益或损耗因子相加为正或负dB值,而不是将其乘以比率。 分贝与功率转化的速读表如下所示:…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...