There is a maze map with some reachable locations and some unreachable locations (obstacles, walls, boundaries). Getting from one position to the next can only be achieved by taking a step up (or right, or down, or left), starting from the beginning and finding a path to the end.

A two-dimensional matrix is used to simulate a maze map, where 1 means the location is unreachable and 0 means the location is reachable. Mark the corresponding location on the map every time you pass to avoid duplication. After finding the path, print the coordinates of each step and finally reach the destination position.

Encapsulate Dot, Block for depth-first traversal, and WideBlock for breadth-first traversal.

backtracking

From each position, there are four options for the next step (top, right, bottom, left). First, choose one direction. If you can go in that direction, go in that direction and switch to the next position. If you can’t go, go in another direction. If you can’t go in all directions, exit the current position and go to the previous position. The current position changes to the previous position. Do this consistently, if the current position is the end, then end. If you go through all the paths and you don’t get there, there’s no solution. Here’s the code:

Public static void main(String[] args) {public static void main(String[] args) {int[][] map = new int[8][7]; // use 1 for the wall // set the top and bottom to 1for(int i = 0; i < 7; i++) { map[0][i] = 1; map[7][i] = 1; } // set both sides to 1for(int i = 0; i < 8; i++) { map[i][0] = 1; map[i][6] = 1; } map[3][1] = 1; map[3][2] = 1; // map[1][2] = 1; // map[2][2] = 1; // Output map system.out.println ("The state of the map");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + ""); } System.out.println(); } // Use recursive backtracking to find the path for the ball //setWay(map, 1, 1);
        setWay2(map, 1, 1); // Outputs the new map, the ball walks through, and identifies the recursion system.out.println ("What happened to the map that the ball walked on and marked.");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + ""); } System.out.println(); }} // Use recursive backtracking to find the way for the ball // description //1. Map indicates the map //2. I and j indicate where to start on the map (1,1) //3. If the ball can reach map[6][5], the pathway is found. //4. Convention: When map[I][j] is 0, it means that the point has not passed. When it is 1, it means the wall. 2 indicates that the channel can go. 3 indicates that the point has been passed but cannot be reached //5. In the maze, a strategy (method) should be determined: down -> right -> up -> left. If the point cannot be reached, /** ** @param map indicates where the map * @param I starts looking for * @param j * @returnIf it finds a path, it returnstrueOtherwise returnfalse
     */
    public static boolean setWay(int[][] map, int i, int j) {

        if(map[6][5] == 2){
            return true;
        } else if(map[i][j] == 0){
            map[i][j]=2;
            if(setWay(map,i+1,j)) {
                return true;
            } else if(setWay(map,i,j+1)){
                return true;
            } else if(setWay(map,i-1,j)){
                return true;
            } else if(setWay(map,i,j-1)){
                return true;
            }else{
                map[i][j]=3;
                return false; }}else{
            return false; }} // Change the path finding policy to up -> right -> Down -> left public static BooleansetWay2(int[][] map, int i, int j) {
        if(map[6][5] == 2) {// The path has found OKreturn true;
        } else {
            if(map [I] [j] = = 0) {/ / if the current point is not walk / / in accordance with the strategy - > right - > - > left on the map [I] [j] = 2; // Assume that the point is open.if(setWay2(map, i-1, j)) {// Go upreturn true;
                } else if (setWay2(map, I, j+1)) {// go rightreturn true;
                } else if (setWay2(map, I +1, j)) {// downreturn true;
                } else if (setWay2(map, I, j-1)){// go leftreturn true;
                } elseMap [I][j] = 3;return false; }}else{// Map [I][j]! Lambda equals 0, maybe 1, 2, 3return false; }}}}Copy the code

Test results:

Modify the fence data in it,

Maze problem writing some ideas

1. The first thing to determine is the condition for quitting recursion, which can reduce invalid judgment.

2. Control the status of the path. Here, the status of the current node is determined by setting the value of the node (1). Fence, two, go. Three, go.

3. Set the node status to indicate the path.

How to find the shortest path idea

General train of thought

1. List all possible paths such as policy (method) down -> right -> up -> left, and store each case in an array.

2. Run the calculations with each strategy, save the results,

3. Calculate the number of nodes equal to 2 in each result, i.e. the length of the path.

4. Obtain the shortest path after comparison

To be continued…