java 实现迷宫回溯算法示例详解
作者:Lzfa 发布时间:2023-12-14 23:52:26
标签:java,迷宫回溯,算法
用一个7 x 7的矩形表示迷宫,0和1分别表示的是通路和障碍。通过设计编写程序找到蓝色小球达到蓝色旗子的路线
思路:
构建一个迷宫(用二维数组)实现找通路的方法findRoad()
构建二维数组不难,我们主要是要实现findRoad()这个方法,在实现这个方法前,我们需要约定好一下几个点:小球的位置当作入口(1,1),小旗的位置当作出口(5,5)数组里数的含义分别为(0没有走过)、(1障碍)、(2走过且为正确的路线)、(3走过且为错误的路线)将我们每一步的走法称为策略:下 -> 右 -> 上 ->左
实现
首先构建出迷宫
public static void main(String[] args) {
//1.创建二维数组模拟迷宫
int[][] maze = new int[7][7];
//2.初始化迷宫
for (int i = 0; i < maze.length; i++) {
//maze[i][j]:i控制行 j:控制列
maze[0][i] = 1;//第1行都为1
maze[6][i] = 1;//最后一行都为1
maze[i][0] = 1;//第一列都为1
maze[i][6] = 1;//最后一列都为1
//其他位置的1
maze[4][1] = 1;
maze[4][2] = 1;
maze[4][3] = 1;
maze[4][4] = 1;
maze[3][4] = 1;
maze[2][3] = 1;
}
//打印迷宫
System.out.println("完成迷宫初始化:");
for (int i = 0; i < maze.length; i++) {
for (int j = 0; j < maze[i].length; j++) {
System.out.print(maze[i][j] + " ");
}
System.out.println();
}
}
然后写findRoad()方法
* 使用递归回溯找通路 (5,5为出口)
* @param maze 迷宫
* @param i 从哪个位置开始找
* @param j 从哪个位置开始找
* @return 找到通路返回true 否则false
*/
public static boolean findRoad(int[][] maze, int i, int j) {
//策略:下 -> 右 -> 上 ->左
//0:没有走过 1:障碍 2:走过且为正确的路线 3:走过且为错误的路线
if (maze[5][5] == 2) {//找到通路
return true;
} else {
if (maze[i][j] == 0) {
//当前点没走过,按策略走
maze[i][j] = 2;//当前点改为2,假定能走通
if (findRoad(maze, i + 1, j)) {//向下走
return true;
} else if (findRoad(maze, i, j + 1)) {//向右走
return true;
} else if (findRoad(maze, i - 1, j)) {//向上走
return true;
} else if (findRoad(maze, i, j - 1)) {//向左走
return true;
} else {
//该点无法走通
maze[i][j] = 3;
return false;//返回到上个方法(即返回到上个点)
}
} else {
//该点为 1或2或3,无法走通,直接返回上个方法(即上个点)
return false;
}
}
}
main方法调用findRoad()方法,传入创建好的迷宫,和入口点(1,1)
//mian方法中调用findRoad()方法
findRoad(maze,1,1);
//打印迷宫
System.out.println("完成路线的迷宫:");
for (int i = 0; i < maze.length; i++) {
for (int j = 0; j < maze[i].length; j++) {
System.out.print(maze[i][j] + " ");
}
System.out.println();
}
效果
来源:https://blog.csdn.net/weixin_47254987/article/details/107666338


猜你喜欢
- Flutter中的生命周期类似于Vue、React中的生命周期一样,有初始化、状态更新、停用、销毁等。在React中,组件分为函数式组件和类
- 本文研究的主要是Java编程中的复用类,那么到底复用类是什么东西,又有什么用法,下面具体介绍。看了老罗罗升阳的专访,情不自禁地佩服,很年轻,
- 环境配置:jdk1.8mybatis3.4.1springboot2.0起始原因:编写mybatis的Demo程序时,mapper传递多参数
- 线程中断机制提供了一种方法,用于将线程从阻塞等待中唤醒,尝试打断目标线程的现有处理流程,使之响应新的命令。Java 留给开发者这一自由,我们
- 一、背景介绍在微服务都是以HTTP接口的形式暴露自身服务的,因此在调用远程服务时就必须使用HTTP客户端。我们可以使用JDK原生的URLCo
- 本文实例为大家分享了Android自定义view贝塞尔曲线,供大家参考,具体内容如下贝塞尔曲线以一个简单的贝塞尔曲线为例,二阶曲线原理贝塞尔
- Android 读取资源文件实例详解本文主要介绍 Android 读取资源文件,直接从 assets 读取,从 Raw 文件中读取,Inpu
- springboot @ConfigurationProperties和@PropertySource区别@ConfigurationPro
- 目录UI组件封装的考虑要点文本输入框接口定义代码实现组件使用踩坑记录总结UI组件封装的考虑要点封装一个 UI 组件,通常需要考虑下面这三个点
- 投影(Projection) 是一种可以将查询结果进行 塑性 的一种操作,你可以使用 投影 将一个 object 转成仅包含你需要属性的新对
- 具体代码如下所示:/// <summary> /// 启用事务提交多条带参数的SQL语句 /// </summary>
- File类概述File类是java.io包下代表与平台无关的文件和目录。File可以新建、删除、重命名文件和目录,但是不能访问文件内容本身,
- Spring使用AOP完成统一结果封装起因:自己写项目的时候忍受不了每个方法都要写一个retrun Result.success();和 r
- SpringBoot项目jar发布获取jar包所在目录路径ApplicationHome ah = new ApplicationHome(
- 前端代码:<form id= "uploadForm"> <p >指定文件名:
- Java-JDK * (AOP)使用及实现原理分析第一章:代理的介绍介绍:我们需要掌握的程度 * (理解) 基于反射机制掌握的程度:1.
- 不想废话,直接写了!因为是留给自己做随笔的,所以大神们看到别喷…… 1.必须有微信公众账号 2.你也可以申请测试微信号,
- 最近项目需要通过经纬度查询 具体的地址和区域名称,通过查询网络资源,发现提供的大多是得到具体的地址而对区域或城市名称的获取就不是很好把握;在
- Android的WebView做不到ios的WebView那样可以很方便的直接预览pdf文件。要实现利用WebView预览pdf我们可以使用
- 介绍在 C/C++ 中,程序员负责对象的创建和销毁。通常程序员会忽略无用对象的销毁。由于这种疏忽,在某些时候,为了创建新对象,可能没有足够的