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
0
投稿
猜你喜欢
- 我们讲一下Criteria查询,这个对于不是太熟悉SQL语句的我们这些程序员来说是很容易上手的。 废话不多说,看一下例子:&nbs
- 1.栈和队列的共同特点是(只允许在端点处插入和删除元素)4.栈通常采用的两种存储结构是(线性存储结构和链表存储结构)5.下列关于栈的叙述正确
- 一、需求分析:1、输入一个数组-----------------------------------------》程序要接收一组输入的数组,
- 本文实例为大家分享了Java实现颜色渐变效果的具体代码,供大家参考,具体内容如下RGB色彩,在自然界中肉眼所能看到的任何色彩都可以由红(R)
- 开篇语Synchronized,Java 友好的提供了的一个关键字,它让开发者可以快速的实现同步。它就像一个星星,远远看去就是一个小小的点。
- 这篇会深化View拖拽实例,利用Flutter Animation、插值器以及AnimatedBuilder教大家实现带动画的抽屉效果。先来
- 这篇文章主要介绍了Spring Boot Debug调试过程图解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值
- 一、流程和任务的关系以下是一个简单的请假流程图,其中有一个开始事件,两个用户任务,一个结束事件。启动流程后,activiti会自动创建第一个
- 前言在RequestMappingHandlerAdapter对request进行了适配,并且调用了目标handler之后,其会返回一个Mo
- 前言xxljob 是采用 java 开发的开源的任务调度系统,架构上分为调度管理器、执行器,目前除了官方提供的 java 执行器外,也有 g
- (注意:本文基于JDK1.8) 前言包括迭代器中的remove()方法,以及删除单个元素、删除多个元素、删除所有元素、删除不包含的
- 下面是一个邮件接收的工具类,有点长!!!public class ReciveMail { private MimeMessage msg
- 最近的项目中要实现一个聊天的功能,类似于斗鱼TV的聊天室功能,与服务器端人商量后决定用WebSocket来做,但是在这之前我只知道Socke
- java与JSON数据的转换实例详解JSON与JAVA数据的转换(JSON 即 JavaScript Object Natation,它是一
- 让我们来看看这段代码: import java.util.BitSet;import java.util.concurrent.C
- 改了个bug,发现这个东西以前不知道,搜索了一下,看到的都是长篇大论,还谈js的源码,也是醉了。我就简单的说说这个是干啥的。简单说:就是触发
- 最近在开发的过程当中,对于已有的代码,想将相关类绘制成UML类图,虽然现在有很多UML类图的优秀软件,比如ProcessOn(可视化编辑)、
- 1.首先,八种基本数据类型分别是:int、short、float、double、long、boolean、byte、char; &
- 在我们的程序设计中,我们经常要加密一些特殊的内容,今天总结了几个简单的加密方法,分享给大家!如何用JAVA实现字符串简单加密解密?为保证用户
- 类注解@component 标注类,泛指各种组件,类不属于各种分类的时候,用它做标注。@Service 标注类,声明该类为业务层组件,用于处