java 实现迷宫回溯算法示例详解
作者:Lzfa 时间:2023-12-14 23:52:26
用一个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
标签:java,迷宫回溯,算法
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
C语言文件操作之fread函数详解
2023-07-06 18:24:15
![](https://img.aspxhome.com/file/2023/7/103077_0s.jpg)
Android 创建与解析XML(五)——详解Dom4j方式
2022-06-15 17:08:51
![](https://img.aspxhome.com/file/2023/8/109218_0s.png)
Android开发中Toast显示消息的方法小结
2023-07-31 20:29:14
浅谈Java的虚拟机结构以及虚拟机内存的优化
2021-12-01 21:59:49
![](https://img.aspxhome.com/file/2023/1/64921_0s.jpg)
新手入门Jvm--jvm概览
2023-11-09 15:42:31
![](https://img.aspxhome.com/file/2023/8/71878_0s.png)
java如何获取map中value的最大值
2023-04-11 05:12:04
jQuery.event.trigger()的简单解释
2023-05-24 03:41:37
![](https://img.aspxhome.com/file/2023/2/62232_0s.png)
Java语法基础之函数的使用说明
2022-07-20 15:55:09
jdk线程池的实现
2023-07-05 18:44:35
![](https://img.aspxhome.com/file/2023/1/88751_0s.jpg)
如何使用BufferedReader循环读文件
2022-04-20 17:32:23
![](https://img.aspxhome.com/file/2023/4/84174_0s.png)
android图像绘制(四)自定义一个SurfaceView控件
2022-09-27 11:28:07
![](https://img.aspxhome.com/file/2023/8/139438_0s.jpg)
JAVA集合框架Map特性及实例解析
2021-06-05 02:23:39
Android实现锁屏荧光效果
2023-09-02 03:12:03
![](https://img.aspxhome.com/file/2023/4/108254_0s.gif)
图解红黑树及Java进行红黑二叉树遍历的方法
2023-04-20 22:09:14
![](https://img.aspxhome.com/file/2023/1/83021_0s.png)
C#实现带百分比的进度条功能示例
2023-09-08 14:17:03
Unity实现本地文本多语言化
2023-05-19 21:58:50
![](https://img.aspxhome.com/file/2023/2/108782_0s.jpg)
c#源码的执行过程详解
2023-10-01 17:03:37
![](https://img.aspxhome.com/file/2023/5/113725_0s.png)
java实现发送邮箱验证码
2022-07-05 07:40:07
![](https://img.aspxhome.com/file/2023/6/83436_0s.jpg)
基于android studio的layout的xml文件的创建方式
2022-10-31 10:52:06
![](https://img.aspxhome.com/file/2023/3/138563_0s.jpg)
C#泛型的使用及示例详解
2022-03-14 07:01:59
![](https://img.aspxhome.com/file/2023/0/89760_0s.png)