JS实现“老鼠走迷宫”算法

2023-11-04 06:10
文章标签 算法 实现 js 迷宫 老鼠

本文主要是介绍JS实现“老鼠走迷宫”算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题描述

给定一个二维数组,数组中2表示墙壁,0表示通路,由此数组可展示为一个迷宫图。给定入口位置和出口位置,判断之间是否存在通路并显示出走出迷宫的道路。

思路

实际上是使用回溯算法求解该问题,就是在上下左右四个方向试探,倘若有路则走一步,在新的位置继续在四个位置试探,并且对走过的路进行标记,倘若走到死胡同里,则退回上一步再来试探,以此类推,使用递归来实现。

JS代码

//递归实现老鼠走迷宫算法
// 定义的迷宫
let maze = [["2","2","2","2","2","2","2","2","2"],  ["2","0","0","0","0","0","0","0","2"],  ["2","0","2","2","0","2","2","0","2"],  ["2","0","2","0","0","2","0","0","2"],  ["2","0","2","0","2","0","2","0","2"],  ["2","0","0","0","0","0","2","0","2"],  ["2","2","2","2","2","2","2","0","2"],  ["2","0","0","0","0","0","0","0","2"],  ["2","2","2","2","2","2","2","0","2"]  
] 
begin_x = 1;           //迷宫入口横坐标
begin_y = 1;           //迷宫入口纵坐标
end_x = 8;             //迷宫出口横坐标
end_y = 7;             //迷宫出口纵坐标
let flag = false;      //定义标志位,判断老鼠有没有出迷宫
let total = 0;         //有多少条路线可以出去
let loop = maze.slice(0);  //数组深拷贝,用于绘制路线。切忌maze_loop = maze;这是浅拷贝。 //设计算法让老鼠移动
function findLoop(arr,start_x,start_y){arr[start_x][start_y] = 1;    //走一步做一个标记,表明已经走过这个格子了,不能走这个格子,只能往下走。loop[start_x][start_y] = '#'; //标记路线//到达迷宫出口if((start_x===end_x)&&(start_y===end_y)){flag=true;console.log(loop);  //打印迷宫路线}else if(flag!==true){try{//定义上 下 左 右移动if(arr[start_x][start_y-1]==0&&!flag){findLoop(arr,start_x,start_y-1)}if(arr[start_x][start_y+1]==0&&!flag){findLoop(arr,start_x,start_y+1)}if(arr[start_x-1][start_y]==0&&!flag){findLoop(arr,start_x-1,start_y)}if(arr[start_x+1][start_y]==0&&!flag){findLoop(arr,start_x+1,start_y)}if(!flag){//如果走不通了,我就倒回去,把最开始的标记清除。重新选择另一条路。loop[start_x][start_y] = "0";arr[start_x][start_y] = "0";}}catch(error){//避免因没有找到出去的路,而造成死循环,堆栈溢出console.log('这个迷宫没有出路',error);}}return flag==false?'真遗憾,小老鼠走不出去了':'小老鼠成功走出迷宫';
}
findLoop(maze,begin_x,begin_y)

结果

定义的迷宫

其中"#"表示小老鼠走出去的路线
迷宫路线图

这篇关于JS实现“老鼠走迷宫”算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/343771

相关文章

golang版本升级如何实现

《golang版本升级如何实现》:本文主要介绍golang版本升级如何实现问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录golanwww.chinasem.cng版本升级linux上golang版本升级删除golang旧版本安装golang最新版本总结gola

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型(范围、哈希、列表、键值),主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区(Range Partitioning1、新建分区表:2、分

MySQL 定时新增分区的实现示例

《MySQL定时新增分区的实现示例》本文主要介绍了通过存储过程和定时任务实现MySQL分区的自动创建,解决大数据量下手动维护的繁琐问题,具有一定的参考价值,感兴趣的可以了解一下... mysql创建好分区之后,有时候会需要自动创建分区。比如,一些表数据量非常大,有些数据是热点数据,按照日期分区MululbU

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一:使用GROUP BY和HAVING子句方法二:仅返回重复值方法三:返回完整记录方法四:

IDEA中新建/切换Git分支的实现步骤

《IDEA中新建/切换Git分支的实现步骤》本文主要介绍了IDEA中新建/切换Git分支的实现步骤,通过菜单创建新分支并选择是否切换,创建后在Git详情或右键Checkout中切换分支,感兴趣的可以了... 前提:项目已被Git托管1、点击上方栏Git->NewBrancjsh...2、输入新的分支的

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

使用Python实现可恢复式多线程下载器

《使用Python实现可恢复式多线程下载器》在数字时代,大文件下载已成为日常操作,本文将手把手教你用Python打造专业级下载器,实现断点续传,多线程加速,速度限制等功能,感兴趣的小伙伴可以了解下... 目录一、智能续传:从崩溃边缘抢救进度二、多线程加速:榨干网络带宽三、速度控制:做网络的好邻居四、终端交互