详解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


猜你喜欢
- 网上查找资料要么是细节不够失败要么是根本没用也不需要这么复杂,在这里总结一下本人在宝塔部署前端和后端的方法。1.在宝塔上添加站点&u
- 本文实例为大家分享了java实现学生成绩管理系统的具体代码,供大家参考,具体内容如下/* *@copyright by LzyRa
- 一、什么是简单工厂模式简单工厂模式又称为静态工厂模式,实质是由一个工厂类根据传入的参数,动态决定应该创建哪一个产品类(这些产品类继承自一个父
- 问题描述如果直接获取某个json数组中的元素将得到如下的json{ "44": { "height
- 事件监听其实我们并不陌生,简单来讲,当程序达到了某个特定的条件,程序就会自动执行一段指令。在spring 中也一样,我们可以使用spring
- 项目要用到Webview和js交互,查了查以前的项目感觉还是有必要整理下的。 简单描述下项目中用到的地方,比如说在web页需要用到登录的地方
- 本文所要介绍的简易天气App主要用RxAndroid、MVP、Retrofit实现,首先来看看效果:主页内容:右侧栏天气列表:左侧栏城市列表
- 本文为大家分享了Android自动检测版本及自动升级的具体代码,供大家参考,具体内容如下步骤:1.检测当前版本的信息AndroidManif
- 前言Java泛型这个特性是从JDK 1.5才开始加入的,因此为了兼容之前的版本,Java泛型的实现采取了“伪泛型”的策略,即Java在语法上
- 曾几何时,我们写代码的时候,每次写Bean的时候都会使用快捷键生成get/set方法,有时候我经常会想,既然每一个Bean我们都会给其提供g
- 话说为了防止 * ,业内有不成文规定,手机公司在做camera时,点击拍照和录像键的时候,必须要有提示音。因此,google也就非常人性化的将
- cookie和session的区别和联系cookie是本地客户端用来存储少量数据信息的,保存在客户端,用户能够很容易的获取,安全性不高,存储
- 最近在项目开发中,使用spring boot+mybatis的架构,数据库设计主键id时定义为bigint类型,使用mybatis的自动生成
- Mybatis 有两种实现方式其一:通过xml配置文件实现其二:面向接口编程的实现  
- hbase是运行在Hadoop上的NoSQL数据库,它是一个分布式的和可扩展的大数据仓库,也就是说HBase能够利用HDFS的分布式处理模式
- 在上一篇文章:Flutter进阶—实现动画效果(二)的最后,我们实现了一个控件,其中包含各种布局和状态处理控件。以及使用自定义的动画感知绘图
- 使用要点如下:1.利用ListAdapter(一般使用ArrayAdapter)为AutoCompleteTextView提供数据,若有需要
- 一、简介   Seata 是一款开源的分布式事务解决方案,致力于在微服务架构下提供高性能和简单易用的分布
- 前言:这两天在整WebApi的服务,由于调用方是Android客户端,Android开发人员也不懂C#语法,API里面的接口也不能直接给他们
- 本文实例为大家分享了Android实现滑动标尺选择值,效果图1.自定义属性attrs.xml<declare-styleable na