当前位置: 首页 > 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值,而不是将其乘以比率。 分贝与功率转化的速读表如下所示:…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...