文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

怎么用Java深度优先遍历解决迷宫问题

2023-06-29 02:03

关注

本文小编为大家详细介绍“怎么用Java深度优先遍历解决迷宫问题”,内容详细,步骤清晰,细节处理妥当,希望这篇“怎么用Java深度优先遍历解决迷宫问题”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。

什么是深度优先

什么是深度,即向下,深度优先,即向下优先,一口气走到底,走到底发现没路再往回走。

在算法实现上来讲,深度优先可以考虑是递归的代名词,深度优先搜索必然需要使用到递归的思路。

有的人可能会说了,我可以用栈来实现,以迭代的方式,那么问题来了,栈这种数据结构,同学们认为是否也囊括了递归呢?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方法是临界判断函数,如下:

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即可。

读到这里,这篇“怎么用Java深度优先遍历解决迷宫问题”文章已经介绍完毕,想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会,如果想了解更多相关内容的文章,欢迎关注编程网行业资讯频道。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯