迷宫问题的 JAVA 递归实现
最编程
2024-06-29 21:18:21
...
问题描述:如下图,小球从起始点找到出迷宫的点,红色为墙体,不可以走
说明:
递归需要遵守的重要规则
-
执行一个方法时,就创建一个新的受保护的独立空间(栈空间)
-
方法的局部变量是独立的,不会相互影响, 比如 n 变量
-
如果方法中使用的是引用类型变量(比如数组),就会共享该引用类型的数据.
-
递归 必须向退出递归的条件逼近,否则就是无限递归,出现 *Error
-
当一个方法执行完毕,或者遇到 return,就会返回, 遵守谁调用,就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕
//代码实现
/**
* @author szw
*/
public class MiGong {
public static void main(String[] args) {
//建立一个8行7列二维数组充当地图
int[][] map = new int[8][7];
for (int j = 0; j < 7; j++) {
map[0][j] = 1;
map[7][j] = 1;
}
for (int i = 0; i < 8; i++) {
map[i][0] = 1;
map[i][6] = 1;
}
map[3][1] = 1;
map[3][2] = 1;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
System.out.println("小球走过迷宫之后的地图:");
find(map, 1, 1);
//小球走过迷宫之后的地图
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}
/**
* 迷宫找路
* 说明:0为未走过,1为墙体,2为走过,3为此点不能成为通路上的点
* @param map 地图
* @param i i,j为其实位置
* @param j
* @return
*/
public static boolean find(int[][] map, int i, int j) {
//如果要找的位置,即map[6][5] 为2,说明路已找到,直接返回true
if (map[6][5] == 2) {
return true;
} else {
if (map[i][j] == 0) {
map[i][j] = 2;
//如果map[i][j] == 0,说明初始位置没有走过,可以走,标记为2,然后开始下一步(开始递归调用)
// 按照 下->右->上->左 的顺序找路
if (find(map, i + 1, j)) {
return true;
} else if (find(map, i, j + 1)) {
return true;
} else if (find(map, i - 1, j)) {
return true;
} else if (find(map, i, j - 1)) {
return true;
} else {
//说明此点走不通,标记为3,此时将结果返回到上一个调用栈,并开始回溯到上一个点,继续按照策略走
map[i][j] = 3;
return false;
}
} else {
//说明map[i][j] != 0,那么就为1,2或3,即都走不通,直接返回false
return false;
}
}
}
}
测试结果:
最后的线路是根据策略生成的,例如此例中,是按照下->右->上->左的策略走的,不同的策略会生成不同的线路,也会产生一个最短路径的问题
上一篇: 前端算法:迷宫问题
下一篇: 利用递归回溯法解决迷宫问题
推荐阅读
-
在 ts 中实现类 java hashmap 的简单方法
-
[阅读笔记 - 解密超大规模集成电路设计方法] 问题 6:实现超大规模集成电路(VLSI)设计的主要方法是什么?
-
使用 Java 实现 PDF 到 HTML 的转换
-
Java string.split 分离出对 List
判断的空值问题 -
Java HashMap 的数据结构和基本原理及其在 Jdk8、Jdk11 和 Jdk17 中的一些变化,以及一些常见问题。
-
个人健康系统|个人健康数据管理系统|基于applet+java的个人健康数据管理系统设计与实现(源代码+数据库+文档)
-
原创] java+swing+mysql小说管理系统的设计与实现
-
IDEA 编译错误 "java: constant string is too long "的解决方法--二、问题的原因
-
计算机毕业设计 智能物业服务系统的设计与实现 Java 实用项目 含源代码 + 文档 + 视频讲解
-
Java 基础 - 单例模式的实现 - 实现方式