Reference: Aha! Algorithm "

1, topic

The plumber's game refers to the matrix as shown in the figure below. There are two kinds of pipes, one is straight and the other is curved. All pipes can rotate freely, and the final goal is to connect the water inlet to the water outlet. The trees are obstacles.

2. Algorithm idea

In this paper, the depth first search algorithm is used to identify the direction of the water inlet, expand according to the direction of the water inlet each time when exploring a new pipeline, and then judge the direction of the next node according to the type of pipeline.

3, code

package search.Breadth first search BFS.Plumber's game;

import java.util.Scanner;

public class Main {
    private static int[][] map;         //Storage pipeline diagram
    private static int n, m, top;       //Matrix x, y, top stack top element of pipeline
    private static boolean[][] status;  //Used or not
    private static String[] stack;      //Stack

    /**
     *
     * @param x Coordinate x
     * @param y Coordinate y
     * @param direction Water inlet direction: 1 up, 2 right, 3 down, 4 left
     */
    private static void  dfs(int x, int y, int direction){
        if(x == n-1 && y == m){     //If to the next exit, it means to complete a path
            System.out.println("Search to connectivity route");
            for (int i = 0; i < top;i++){
                System.out.print(stack[i]+"->");
            }
            System.out.println();
            return ;
        }

        if(y < 0 || x < 0|| x > n-1 || y > m-1 || status[x][y])
            return;

        status[x][y] = true;
        stack[top] = "("+(x+1)+","+(y+1)+","+direction+")";     //Push
        top++;


        if (5 <= map[x][y] && map[x][y] <= 6){      //If it's straight pipe
            switch (direction){
                case 1:
                    dfs(x+1, y, direction);
                    break;
                case 2:
                    dfs(x, y-1, direction);
                    break;
                case 3:
                    dfs(x-1, y, direction);
                    break;
                case 4:
                    dfs(x, y+1, direction);
                    break;
            }

        }else{
            switch (direction){     //Curved pipe
                case 1:
                    dfs(x, y-1, 2);
                    dfs(x, y+1, 4);
                    break;
                case 2:
                    dfs(x-1, y, 3);
                    dfs(x+1, y, 1);
                    break;
                case 3:
                    dfs(x, y-1, 2);
                    dfs(x, y+1, 4);
                    break;
                case 4:
                    dfs(x-1, y, 3);
                    dfs(x+1, y, 1);
                    break;
            }
        }

        status[x][y] = false;
        top--;
    }

    public static void main(String[] ages){
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();

        map = new int[n][m];
        status = new boolean[n][m];
        stack = new String[n*m];
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                map[i][j] = scanner.nextInt();
            }
        }

        dfs(0,0, 4);
    }
}

/**
 Test data:
 5 4
 5 3 5 3
 1 5 3 0
 2 3 5 1
 6 1 1 5
 1 5 5 4
 Result:
 Search to connectivity route
 (1,1,4)->(1,2,4)->(2,2,1)->(3,2,1)->(3,3,4)->(3,4,4)->(4,4,1)->(5,4,1)->
 */