Shulou(Shulou.com)06/01 Report--

In this article, the editor introduces in detail "how to use Java depth priority traversal to solve the maze problem", the content is detailed, the steps are clear, and the details are handled properly. I hope this "how to use Java depth priority traversal to solve the maze problem" article can help you solve your doubts.

What is depth first?

What is depth, that is, downward, depth first, that is, downward priority, go to the end in one breath, go to the end and find there is no way back.

In terms of algorithm implementation, depth first can be considered as a synonym for recursion, and depth first search must use the idea of recursion.

Some people may say, I can use the stack to implement, in an iterative way, so the question is, does the data structure of the stack also include recursion? The method area of the Java language itself is implemented on a stack space.

A simple example.

We take a simple maze as an example, with 1 for the wall and 0 for the path, and we construct a maze with entrances and exits.

1 1 0 1 1 1

1 0 0 0 1 1

1 0 1 1 1 0 1 1

1 0 0 0 1 0 0 1

1 1 1 0 1

With the above 0 as the entrance and the lower 0 as the exit, then the depth-first algorithm traverses the order, the direction traverses in the lower-left and upper-right order, and takes dp [0] [2] as the entrance. I list this process below:

Step one:

Dp [0] [2]-> dp [1] [2]

Step 2:

Dp [1] [2]-> dp [1] [1]

Step 3:

Dp [1] [1]-> dp [2] [1]

Step 4:

Dp [2] [1]-> dp [3] [1]

Step 5:

Dp [3] [1]-> dp [3] [2]

Step 6:

Dp [3] [2]-> dp [3] [3]

Step 7:

Dp [3] [3]-> dp [3] [4]

Step 8:

Dp [3] [4]-> dp [3] [5] because dp [3] [5] is a wall, the depth first algorithm needs to start fallback, and eventually fall back to the position of dp [1] [2], then go right.

Step 8:

Dp [1] [2]-> dp [1] [3]

Step 9:

Dp [1] [3]-> dp [1] [4]

Step 10:

Dp [1] [4]-> dp [1] [5]

Step 11:

Dp [1] [5]-> dp [1] [6]

Step 12:

Dp [1] [6]-> dp [2] [6]

Step 13:

Dp [2] [6]-> dp [3] [6]

Step 14:

Dp [3] [6]-> dp [3] [7]

Step 15:

Dp [3] [7]-> dp [4] [7] end point, program exits

It can be found that the depth-first algorithm is a bit like our life, which requires constant trial and error, and then retreat until we find a way to the exit.

Now let's implement the above steps in code.

Program realization

To solve this problem in a depth-first way, we mainly consider two points, the first is how to expand the nodes, our order is left, bottom, right, top, so how should we achieve this? The second point is how to achieve depth first, although it must be recursive in principle, but how should it be recursive? To solve these two problems, look at the sample code, taking Java as an example:

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 cache) {System.out.println (currentY + "" + currentX); if (currentX = = chux & & currentY = = chuy) {return 1 } / / TODO: enumerate child nodes on 2022-1-11, left, lower and right 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 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;}

As you can see, the core code here is the dfs function. Let's take an in-depth analysis of the wave.

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 enumerates child nodes, left lower right int [] x = new int [] {- 1,0,1,0} Int [] y = new int [] {0,1,0,-1}; for (int I = 0; I < 4; iTunes +) {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 + "result path"); return tmp + 1;}} System.out.println (currentY + "" + currentX + "rollback"); return 0;}

First of all, dfs depth priority, the first thing we should write is to judge the termination condition, where the termination condition is to reach the end point, that is, the current horizontal and vertical coordinates are equal to the exit horizontal and vertical coordinates.

Then, we use an array of two directions as the movement scheme, that is,

/ / TODO: 2022-1-11 enumerates child nodes, left, lower and right int [] x = new int [] {- 1, 0, 1, 0}; int [] y = new int [] {0, 1, 0,-1}; for (int I = 0; I < 4; iNode +) {if (canAdd (a, currentX + x [I], currentY + y [I], cache)) {}

This method is compatible with the array type of movement, no matter how much you are moving, it can be matched in the x and y arrays. Four directions are defined, and now we need to think about the process of recursion.

Since I return 1 when I finish, in fact, if everything on this road should be added by 1, so I have the following judgment

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 + "result path"); return tmp + 1;}}

When the result of the sub-dfs is not 0, which means that the sub-dfs can reach the exit, then simply add 1 to the result and return it to the upper layer. If the result of the sub-dfs is 0, which means that the sub-dfs cannot reach the exit, you can simply return 0.

After reading this, the article "how to use Java depth first to solve the maze problem" has been introduced. If you want to master the knowledge points of this article, you still need to practice and use it before you can understand it. If you want to know more about related articles, welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.