详解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 http://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 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) {

IBpLQpr 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 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 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 currenhttp://tX, int currentY, int chux, int chuy, Set 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即可。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。