What is depth first

What is depth, that is, down, depth first, that is, down first, go to the end at one breath, go to the end, and go back when you find there is no way.
In terms of algorithm implementation, depth first can be considered as a pronoun of recursion, and depth first search must use the idea of recursion.
Some people may say that I can use the stack to implement it in an iterative way. Then the question comes. Do students think that the data structure of stack also includes recursion? The method area of the Java language itself is also implemented in a stack space.
​

A simple example

We take a simple maze as an example. 1 represents the wall and 0 represents the path. We construct a maze with access.
​

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
​

With the above 0 as the entry and the following 0 as the exit, the depth first algorithm traverses in the order of bottom left and top right, and dp[0][2] as the entry. I list this process as follows:
Step 1:
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 finally fallback to dp[1][2], and 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 exit
​

It can be found that the depth first algorithm is a bit like our life. We need to constantly try and make mistakes, and retreat when they are wrong until we find a way to the exit.
Now let's implement the above steps in code.

Program implementation

To solve this problem in a depth first way, we mainly consider two points. The first is how to expand nodes. Our order is left, bottom, right and top. Then, what kind of way should we implement this? The second point is how to achieve depth first. Although it must be recursive in principle, how should it be recursive? To solve these two problems, take 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<Integer> cache) {
        System.out.println(currentY + " " + currentX);
        if (currentX == chux && currentY == chuy) {
            return 1;
        }
        // Todo: enumerating child nodes on January 11, 2022, bottom left and top 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 + " Result path");
                    return tmp + 1;
                }
            }
        }
        System.out.println(currentY + " " + currentX + " RollBACK ");
        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: find the entrance on January 11, 2022
                rux = i;
            }
            if (a[n - 1][i].equals("0")) {
                chux = i;
            }
        }
        Set<Integer> cache = new HashSet<>();
        cache.add(rux * 100000 + ruy);
        System.out.println("Print walking process");
        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 ? "Unreachable" : "Reachable, need to walk" + ans + "step");

    }

    public static void main(String[] args) {
        demo();
    }

}

The canAdd method here is a critical judgment function, as follows:

/**
     * Critical judgment
     * @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;
}

As you can see, the core code here is the dfs function. Let's analyze it in depth

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: enumerating child nodes on January 11, 2022, bottom left and top 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 + " Result path");
                return tmp + 1;
            }
        }
    }
    System.out.println(currentY + " " + currentX + " RollBACK ");
    return 0;
}

First of all, dfs depth is preferred. The first thing to write is to judge the termination condition. The termination condition here is to reach the end point, that is, the current abscissa and ordinate are equal to the abscissa and ordinate of the exit.
Then, we use two direction arrays as the moving scheme, that is

// Todo: enumerating child nodes on January 11, 2022, bottom left and top 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)) {
        }
    }

This method is compatible with the movement mode of array type. No matter how many directions you move, it can be matched in x and y arrays. Four directions are defined. Now we need to think about the process of recursion.
Since I return 1 when I finish, in fact, if all on this road should add 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, it means that the sub dfs can reach the exit. Then add 1 to the result and return it to the upper layer directly. If the result of the sub dfs is 0, it means that the sub dfs cannot reach the exit, just return 0 directly.