Java数据结构 递归之迷宫回溯案例讲解
问题介绍：
用二维数组表示一个迷宫，设置迷宫起点和终点，输出迷宫中的一条通路
实现思路：
二维数组表示迷宫：
0表示路且未走过、1表示墙、2表示通路，3表示已经走过但走不通
设置寻路方法setWay，传入地图和坐标参数
默认方向策略：下、右、上、左
假定传入的店没有走过且可以走通，将其值置为2，然后向下寻路，也就是将坐标 (i + 1, j) 传入寻路方法中
进行递归寻路，向下移动后，再次按照方向策略进行寻路，即再向下寻路，直到遇到死路，即下右左均走不通（因为将走过的路置为2，故向上也走不通，即遇到死路时回头不算通路），则将该点置为3，并返回false，回到上一个递归，找寻方向策略中剩下的方向，实现回溯
代码实现：
public class Maze {
public static void main(String[] args) {
maze();
}
//迷宫回溯问题
public static void maze() {
//创建二维数组模拟迷宫
//使用1表示墙，0表示路
int[][] map = new int[][]{
{1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 1},
{1, 0, 1, 0, 0, 0, 1},
{1, 0, 1, 0, 1, 1, 1},
{1, 1, 0, 0, 0, 0, 1},
{1, 0, 1, 1, 0, 1, 1},
{1, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1}
};
//输出地图
System.out.println("迷宫：");
for (int[] row : map) {
for (int i : row) {
System.out.printf("%d\t", i);
}
System.out.println();
}
System.out.println("寻路结果：");
//开始寻路
setWay(map, 1, 1);
//输出地图
for (int[] row : map) {
for (int i : row) {
System.out.printf("%d\t", i);
}
System.out.println("");
}
}
//传入地图map
//传入开始位置(i, j)
//如果能到达右下角(6, 5)，则说明找到通路
//0表示未走过，1表示墙，2表示可以走的通路，3表示已经走过，但是走不通
//确定方向策略：下 -> 右 -> 上 -> 左
//若该点走不通，则回溯
public static boolean setWay(int[][] map, int i, int j) {
if (map[6][5] == 2) {
//通路已经找到
return true;
} else {
if (map[i][j] == 0) {
//如果当前点没有走过
map[i][j] = 2; //假定该点可以走通
if (setWay(map, i + 1, j)) {
//向下走
return true;
} else if (setWay(map, i, j + 1)) {
//向右走
return true;
} else if (setWay(map, i - 1, j)) {
//向上走
return true;
} else if (setWay(map, i, j - 1)) {
//向左走
return true;
} else {
//该点走不通
map[i][j] = 3;
return false;
}
} else {
//如果map[i][j] != 0
//可能是1、2、3
return false;
}
}
}
}
输出结果：
迷宫： 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 寻路结果： 1 1 1 1 1 1 1 1 2 2 2 0 0 1 1 3 1 2 0 0 1 1 3 1 2 1 1 1 1 1 0 2 2 0 1 1 0 1 1 2 1 1 1 0 0 0 2 2 1 1 1 1 1 1 1 1
到此这篇关于Java数据结构之递归之迷宫回溯案例讲解的文章就介绍到这了,更多相关Java数据结构之递归之迷宫回溯内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
什么是递归?用Java写一个简单的递归程序
什么是递归?用Java写一个简单的递归程序 递归的定义 递归(recursion):以此类推是递归的基本思想,将规模大的问题转化为规模小的问题来解决. 递归的要素 自定义递归函数,并确定函数的基本功能 例如Java从键盘输入一个数,求输入这个数的阶乘.这个时候把输入的数字作为形参 int diGuiTest(int n ){ } 找到递归函数循环结束条件 在求阶乘的时候,我们不妨做出如下思考,例如输入的n是5,那么5!是5 * 4 3 * 2 * 1,那是不是可以写成 n f(n-1)?,程序运
-
java栈实现二叉树的非递归遍历的示例代码
一般来说遍历二叉树用到递归,但是用Stack进行遍历也是一个不错的方法. 二叉树设置 class Node{ public int val; public Node left; public Node right; public Node(int v) { val=v; left=null; right=null; } } public class Main { public static void main(String[] args) { Node head =new Node(0); No
-
使用Java将一个List运用递归转成树形结构案例
在开发中,我们会遇到将不同组织架构合并成tree这种树状结构,那么如果做呢? 实际上,我们也可以理解为如何将拥有父子关系的list转成树形结构,而这其中主要的方法就是递归! 1.实体对象: @Data public class Node { private Integer id; private String city; private Integer pid; private List<Node> children; public Node(Integer id,String city,In
-
java如何用递归方法求阶乘
java 用递归方法求阶乘 一个正整数的阶乘,是所有不大于该数的正整数的积,并且0的阶乘为1,n的阶乘写作n!,由1808年基斯顿·卡曼(Christian Kramp,1760-1826)引进这个表示法. java代码: //用递归方法求阶乘 public class Factorial{ public static void main(String[] args){ int N = 5; for(int n = 0; n <= N; n++){ int fact = factorial(n)
-
Java实现简单的递归操作方法实例
前言 在数据结构算法设计中,或者一个方法的具体实现的时候,有一种方法叫做"递归",这种方法在思想上并不是特别难,但是实现起来还是有一些需要注意的.虽然对于很多递归算法都可以由相应的循环迭代来代替,但是对于一些比较抽象复杂的算法不用递归很难理解与实现. 递归分为直接递归和间接递归,就简单分享一下两个小的直接递归. 对于递归的概念,其实你可以简单的理解为自己定义自己,记得小时候看过一部电视剧<狼毒花>,里面主角叫做"常发",但是个文盲,老师问他叫什么,他说&
-
java新人基础入门之递归调用
一.递归概念 递归本质:程序调用自身的编程技巧叫做递归. 程序调用自身的编程技巧称为递归( recursion).递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或说明中有直接或间接调: 用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过: 程所需要的多次重复计算,大大地减少了程序的代码量.递归的能力在于用有限的语句来定义对象的无限集合. 二.递归的三个条件: 边界条件 递归前进段 递归返回段 当
-
java迷宫算法的理解(递归分割,递归回溯,深搜,广搜)
最近这学期做了一个java迷宫的课程设计,这里代码及其算法逻辑就分享出来. 首先简单的说一下其中我使用的算法(自动生成地图:递归分割法.递归回溯法:寻找路径:深度优先.广度优先算法) 递归分割法: 地图外面一圈被墙围住,然后在空白区域生成十字墙壁,再随机选择三面墙,将其打通,这样就能保证迷宫的流动性,再分别对刚才分好的四个区域以同样的方式执行分割,一直递归下去,直到空间不足以分割就return. 递归回溯法: 递归回溯法与深度优先算法在大致算法上其实差不多,具体只有一些细微的差别,都是通过判断当
-
如何利用Java递归解决“九连环”公式
在之前有写到过一点点有关递归的东西点击打开链接,然后想到小时候自己玩的一个玩具--九连环.小时候自己曾经一边玩一边用笔记下来解开这个东西的公式,那是十几年前的事情了.前两天突然想起来,九连环的基本操作就是一个递归,一个感觉起来非常标准的递归过程. 九连环的玩法规则用一句话来概括就是:如果你想要卸掉某一环或者装上某一环,只需要保留这一环前面一环,再之前所有的环都卸掉.(例如你想要卸掉或者装上第9环,那么保留第8环,第8环之前的所有的环都卸掉)其中第一环可以直接卸掉.(其实第一第二这两环可以一起装上
-
Java数据结构 递归之迷宫回溯案例讲解
问题介绍: 用二维数组表示一个迷宫,设置迷宫起点和终点,输出迷宫中的一条通路 实现思路: 二维数组表示迷宫: 0表示路且未走过.1表示墙.2表示通路,3表示已经走过但走不通 设置寻路方法setWay,传入地图和坐标参数 默认方向策略:下.右.上.左 假定传入的店没有走过且可以走通,将其值置为2,然后向下寻路,也就是将坐标 (i + 1, j) 传入寻路方法中 进行递归寻路,向下移动后,再次按照方向策略进行寻路,即再向下寻路,直到遇到死路,即下右左均走不通(因为将走过的路置为2,故向上也走不通,即
-
Java插件扩展机制之SPI案例讲解
目录 什么是SPI 与 接口类-实现类 提供的RPC 方式有什么区别? 假设我们需要实现RPC,是怎么做的? 那RPC究竟跟SPI什么关系? SPI的应用场景 怎么实现一个SPI? 中间件是怎么实现SPI的? Apollo-Client中的实现 JDBC中的实现 什么是SPI SPI ,全称为 Service Provider Interface,是一种服务发现机制.其为框架提供了一个对外可扩展的能力. 与 接口类-实现类 提供的RPC 方式有什么区别? 传统的接口类实现形式为如下 public
-
Java之SpringBoot集成ActiveMQ消息中间件案例讲解
ActiveMQ是Apache提供的开源组件,是基于JMS标准的实现组件.下面将利用SpringBoot整合ActiveMQ组件,实现队列消息的发送与接收. 第一步:引入依赖 第二步:修改application.yml文件,进行ActiveMQ的配置 第三步:定义消息消费监听类 第四步:定义消息生产者业务接口 第五步: 定义消息业务实现类 第六步:定义JMS消息发送配置类 第七步:测试发送消息 查看结果: 本文采用ActiveMQ实现了消息的发送与接收处理.每当有消息接收到时,都会自动执行M
-
Java使用elasticsearch基础API使用案例讲解
1.依赖 我用的是 springboot 2.2.5.RELEASE 版本,这里只贴出主要依赖: <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-data-elasticsearch</artifactId> </dependency> 2.配置+测试源码 这里根据elasticsearch服务端的地址进行
-
Java之字节码以及优势案例讲解
一.Java编译器 Java中引入了虚拟机的概念,即在机器和编译程序之间加入了一层抽象的虚拟的机器,.这台虚拟的机器在任何平台上都提供给编译程序一个共同的接口.编译程序只需要面向虚拟机,生成虚拟机能够理解的代码,然后由解释器来将虚拟机代码来将虚拟机代码转换为特定的系统机器码执行.在Java中,这种提供虚拟机理解的代码叫做字节码(即扩展名为 .class的文件),它不面向任何特定的处理器,仅仅只面向虚拟机. 1.利用记事本写一段Java代码 2.将记事本命名为 hello.java 3.cmd+r
-
Java之Jackson的基本使用案例讲解
Jackson 是当前用的比较广泛的,用来序列化和反序列化 json 的 Java 的开源框架.Jackson 社 区相对比较活跃,更新速度也比较快, 从 Github 中的统计来看,Jackson 是最流行的 json 解析器之一 . Spring MVC 的默认 json 解析器便是 Jackson. Jackson 优点很多. Jackson 所依赖的 jar 包较少 ,简单易用.与其他 Java 的 json 的框架 Gson 等相比, Jackson 解析大的 json 文件速度比较快
-
Java之IO流面试题案例讲解
一.Java中IO流分为几种? 按照流的流向分,可以分为输入流和输出流: 按照操作单元分,可以分为字节流和字符流(字节流可以读写任何单位的数据,字符流只可以读写txt数据): 按照流的角色分,可以分为节点流和处理流: 二.IO中flush()和close()的区别 close()方法具备刷新功能,在关闭流之前就会先刷新缓冲区,将缓冲区的字节全部刷新到文件上,在关闭流.(close()方法包含一次flush()方法) flush()方法可以刷新,并且刷新之后可以继续写,而close()方法刷新之后
-
Java数据结构与算法实现递归与回溯
目录 1.什么是递归? 2.代码案例一——迷宫问题 3.代码案例二——八皇后问题 1.什么是递归? 简单的说: 递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁. 看个实际应用场景,迷宫问题(回溯), 递归(Recursion) 我列举两个小案例,来帮助大家理解递归,这里在给大家回顾一下递归调用机制 打印问题 阶乘问题 public static void test(int n) { if (n > 2) { test(n - 1); }
-
java 实现迷宫回溯算法示例详解
用一个7 x 7的矩形表示迷宫,0和1分别表示的是通路和障碍.通过设计编写程序找到蓝色小球达到蓝色旗子的路线 思路: 构建一个迷宫(用二维数组)实现找通路的方法findRoad() 构建二维数组不难,我们主要是要实现findRoad()这个方法,在实现这个方法前,我们需要约定好一下几个点:小球的位置当作入口(1,1),小旗的位置当作出口(5,5)数组里数的含义分别为(0没有走过).(1障碍).(2走过且为正确的路线).(3走过且为错误的路线)将我们每一步的走法称为策略:下 -> 右 -> 上
-
Java对文件进行基本操作案例讲解
File文件类 java.io.File是文件和目录的重要类(JDK6及以前是唯一) 目录也使用File类进行表示 File类与操作系统无关,但会受到操作系统的权限限制 常用方法 createNewFile , delete , exists , getAbsolutePath , getName , getParent , getPath isDirectory , isFile , length , listFiles , mkdir , mkdirs File不涉及到具体的文件内容.只会涉