详解Java利用深度优先遍历解决迷宫问题
作者:炒鸡辣鸡123 发布时间:2022-08-20 02:46:54
什么是深度优先
什么是深度,即向下,深度优先,即向下优先,一口气走到底,走到底发现没路再往回走。
在算法实现上来讲,深度优先可以考虑是递归的代名词,深度优先搜索必然需要使用到递归的思路。
有的人可能会说了,我可以用栈来实现,以迭代的方式,那么问题来了,栈这种数据结构,同学们认为是否也囊括了递归呢?Java语言的方法区本身也是实现在一个栈空间上的。
一个简单的例子
我们以一个简单的迷宫为例,以1代表墙,0代表路径,我们构造一个具有出入口的迷宫。
1 1 0 1 1 1 1 1 1
1 0 0 0 0 0 0 1 1
1 0 1 1 1 1 0 1 1
1 0 0 0 0 1 0 0 1
1 1 1 1 1 1 1 0 1
以上面这个0为入口,下面这个0为出口,那么深度优先的算法遍历顺序,方向的遍历顺序为左下右上,以dp[0][2]为入口,我把这个过程列在下面了:
第一步:
dp[0][2] -> dp[1][2]
第二步:
dp[1][2] -> dp[1][1]
第三步:
dp[1][1] -> dp[2][1]
第四步:
dp[2][1] -> dp[3][1]
第五步:
dp[3][1] -> dp[3][2]
第六步:
dp[3][2] -> dp[3][3]
第七步:
dp[3][3] -> dp[3][4]
第八步:
dp[3][4] -> dp[3][5] 由于 dp[3][5]是墙,所以深度优先算法需要开始回退,最终会回退到dp[1][2]这个位置,然后向右走
第八步:
dp[1][2] -> dp[1][3]
第九步:
dp[1][3] -> dp[1][4]
第十步:
dp[1][4] -> dp[1][5]
第十一步:
dp[1][5] -> dp[1][6]
第十二步:
dp[1][6] -> dp[2][6]
第十三步:
dp[2][6] -> dp[3][6]
第十四步:
dp[3][6] -> dp[3][7]
第十五步:
dp[3][7] -> dp[4][7] 终点,程序退出
可以发现,深度优先算法有点像我们的人生,需要不断试错,错了就退,直到找到一条通往出口的路。
现在让我们动手用代码实现一下上面的步骤吧。
程序实现
以深度优先的方式解决这个问题,主要考虑两点,首先是如何扩展节点,我们的顺序是左,下,右,上,那么,应该以什么样的方式实现这个呢?第二点,就是如何实现深度优先,虽然原理上肯定是递归,但是应该如何递归呢?要解决这两个问题,请看示例代码,以Java为例:
package com.chaojilaji.book;
import com.chaojilaji.book.util.InputUtils;
import java.util.HashSet;
import java.util.Set;
import static com.chaojilaji.book.util.CheckUtils.canAdd;
public class Dfs {
public static Integer dfs(String[][] a, int currentX, int currentY, int chux, int chuy, Set<Integer> cache) {
System.out.println(currentY + " " + currentX);
if (currentX == chux && currentY == chuy) {
return 1;
}
// TODO: 2022/1/11 枚举子节点,左 下 右 上
int[] x = new int[]{-1, 0, 1, 0};
int[] y = new int[]{0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
if (canAdd(a, currentX + x[i], currentY + y[i], cache)) {
Integer tmp = dfs(a, currentX + x[i], currentY + y[i], chux, chuy, cache);
if (tmp != 0) {
System.out.println(currentY + " " + currentX + " 结果路径");
return tmp + 1;
}
}
}
System.out.println(currentY + " " + currentX + " 回滚");
return 0;
}
public static Integer getAns(String[][] a) {
int m = a[0].length;
int n = a.length;
int rux = -1, ruy = 0;
int chux = -1, chuy = n - 1;
for (int i = 0; i < m; i++) {
if (a[0][i].equals("0")) {
// TODO: 2022/1/11 找到入口
rux = i;
}
if (a[n - 1][i].equals("0")) {
chux = i;
}
}
Set<Integer> cache = new HashSet<>();
cache.add(rux * 100000 + ruy);
System.out.println("打印行走过程");
return dfs(a, rux, ruy, chux, chuy, cache)-1;
}
public static void demo() {
String x = "1 1 0 1 1 1 1 1 1\n" +
"1 0 0 0 0 0 0 1 1\n" +
"1 0 1 1 1 1 0 1 1\n" +
"1 0 0 0 0 1 0 0 1\n" +
"1 1 1 1 1 1 1 0 1";
String[][] a = InputUtils.getInput(x);
Integer ans = getAns(a);
System.out.println(ans == -1 ? "不可达" : "可达,需要行走" + ans + "步");
}
public static void main(String[] args) {
demo();
}
}
这里的canAdd方法是临界判断函数,如下:
/**
* 临界判断
* @param a
* @param x
* @param y
* @param cache
* @return
*/
public static Boolean canAdd(String[][] a, Integer x, Integer y, Set<Integer> cache) {
int m = a[0].length;
int n = a.length;
if (x < 0 || x >= m) {
return false;
}
if (y < 0 || y >= n) {
return false;
}
if (a[y][x].equals("0") && !cache.contains(x * 100000 + y)) {
cache.add(x * 100000 + y);
return true;
}
return false;
}
可以瞧见,这里面最核心的代码在于dfs这个函数,让我们来深入分析一波
public static Integer dfs(String[][] a, int currentX, int currentY, int chux, int chuy, Set<Integer> cache) {
System.out.println(currentY + " " + currentX);
if (currentX == chux && currentY == chuy) {
return 1;
}
// TODO: 2022/1/11 枚举子节点,左 下 右 上
int[] x = new int[]{-1, 0, 1, 0};
int[] y = new int[]{0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
if (canAdd(a, currentX + x[i], currentY + y[i], cache)) {
Integer tmp = dfs(a, currentX + x[i], currentY + y[i], chux, chuy, cache);
if (tmp != 0) {
System.out.println(currentY + " " + currentX + " 结果路径");
return tmp + 1;
}
}
}
System.out.println(currentY + " " + currentX + " 回滚");
return 0;
}
首先,dfs深度优先,首先应该写的是判断终止条件,这里的终止条件就是到达终点,即目前的横纵坐标等于出口的横纵坐标。
然后,我们利用两个方向数组作为移动方案,也就是
// TODO: 2022/1/11 枚举子节点,左 下 右 上
int[] x = new int[]{-1, 0, 1, 0};
int[] y = new int[]{0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
if (canAdd(a, currentX + x[i], currentY + y[i], cache)) {
}
}
这种方法,是数组类型的移动方式的兼容写法,不管你的移动方向有多少,都可以配在x和y两个数组中。定义了四个方向,现在我们需要思考递归的过程。
既然我完成的时候是返回1,那么其实如果在这条路上的所有都应该加1,所以,就有了下面的判断
if (canAdd(a, currentX + x[i], currentY + y[i], cache)) {
Integer tmp = dfs(a, currentX + x[i], currentY + y[i], chux, chuy, cache);
if (tmp != 0) {
System.out.println(currentY + " " + currentX + " 结果路径");
return tmp + 1;
}
}
当子dfs出来的结果不为0,说明该子dfs是可以到达出口的,那么直接把结果加1返回给上层即可。如果子dfs出来的结果为0,说明该子dfs是不能到达出口的,就直接返回0即可。
来源:https://blog.csdn.net/xielinrui123/article/details/122628229
猜你喜欢
- 一、判断一个字符串str不为空的方法有:1、str == null;2、"".equals(str);3、str.len
- 为什么要自定义缓存注解?Spring Cache本身提供@Cacheable、@CacheEvict、@CachePut等缓存注解,为什么还
- 此篇文章内容仅限于 描述springboot与 thy 自定义标签的说明,所以你在看之前,请先会使用springboot和thymeleaf
- 泛型(Generic type 或者 generics)是对 Java 语言的类型系统的一种扩展,以支持创建可以按类型进行参数化的类。可以把
- 生产者消费者模式的几种实现方式拿我们生活中的例子来说,工厂生产出来的产品总是要输出到外面使用的,这就是生产与消费的概念。在我们实际的软件开发
- 本文实例讲述了Android中断线程的处理方法。分享给大家供大家参考。具体方法如下:我现在对一个用户注册的功能1.用ProgressDial
- 简介MyBatis-Plus (opens new window)(简称 MP)是一个 MyBatis (opens new window)
- 本文以实例阐述了C++中形参与实参的区别,有助于读者加深对于C++形参与实参的认识。形参出现在函数定义中,在整个函数体内都可以使用, 离开该
- 在项目中,分页是一个项目中必不可少的,它可以防止我们从数据库中进行大量数据查询时速度变慢,提高我们的查询效率。1、定义分页模型:PageMo
- 本文实例讲述了java在网页上面抓取邮件地址的方法。分享给大家供大家参考。具体实现方法如下:import java.io.BufferedR
- 详解 Corba开发之Java实现Service与Client1 概述
- 本文主要介绍Java Date 日期类型,以及Calendar的怎么获取时间,然后写成时间工具类里面有下面这些方法:- 时间转字符串(有默认
- 注册中心呢 就是springcloud的一个核心组件 所有微服务的基石 微服务的核心思想就是分布式 所有的服务分开管理 但这些服务分开后该如
- 一、栈1.1 概述Java为什么要有集合类: 临时存储数据。链表的本质: 对象间通过持有和引用关系互相关联起来。线性表: 普通线性表, 操作
- 问题描述springcloud项目部署或调试时,占用的内存特别多。当部署到服务器上去后,有可能导致服务器内存占用过多而崩溃。解决方案&nbs
- 导语相信大家无论是做前端还是做后端的,都被接口接口文档所折磨过,前端抱怨接口文档和后端给的不一致,后端抱怨写接口文档很麻烦,所以Swagge
- java里有数字long来表示大的整数,如果两个数字的范围超过了long,要做加法算法怎么做呢?这个问题在面试中经常碰到,如果之前没有经历的
- 本文实例讲述了Java单例模式下的MongoDB数据库操作工具类。分享给大家供大家参考,具体如下:我经常对MongoDB进行一些基础操作,将
- 1、原理事务的概念想必大家都很清楚,其ACID特性在开发过程中占有重要的地位。同时在并发过程中会出现一些一致性问题,为了解决一致性问题,也出
- 前言最近写了一篇博客是关于 使用Jenkins来构建SVN+Maven项目 ,这里使用的的代码版本工具是SVN,但是事实上也有很多公司使用G