Java实现递归求解迷宫通路

深碍√TFBOYSˉ_ 2022-12-05 02:12 178阅读 0赞

package recursion;
    // 递归实现迷宫求解
    public class MazeDemo {
    
        // 寻找路径策略：下->右->上->左
    
        /**
         * 递归寻找解路径，0表示未走过，1表示墙，2表示已走过，3表示不可行
         * @param maze
         * @param i 起点纵坐标
         * @param j 起点横坐标
         * @return
         */
        public static boolean getWay(Maze maze, int i, int j) {
            if (maze.path[maze.d1][maze.d2] == 2) { // 已经找到通路
                return true;
            } else {
                if (maze.path[i][j] == 0) { // 当前路还没走过
                    maze.path[i][j] = 2; // 假定该点可以走通
                    if (getWay(maze, i+1, j)) { // 朝下走
                        return true;
                    } else if(getWay(maze, i, j+1)) { // 朝右走
                        return true;
                    } else if(getWay(maze, i-1, j)) { // 朝上走
                        return true;
                    } else if(getWay(maze, i, j-1)) { // 朝左走
                        return true;
                    } else {
                        maze.path[i][j] = 3;
                        return false;
                    }
                } else { // 如果maze.path[i][j]!=0，可能是1，2，3
                    return false;
                }
            }
        }
    
        public static void main(String[] args) {
            // 初始化一个8*8的迷宫，终点设置为(6, 6)
            Maze maze = new Maze(8, 8, 6, 6);
            // 设置墙
            maze.setWall(1, 2);
            maze.setWall(2, 2);
            maze.setWall(2, 3);
            maze.setWall(2, 4);
            maze.setWall(3, 4);
            maze.setWall(4, 2);
            maze.setWall(4, 4);
            maze.setWall(5, 2);
            maze.setWall(5, 4);
            maze.setWall(5, 5);
            maze.setWall(6, 2);
    
            System.out.println("初始化迷宫为");
            maze.printMaze();
    
            if (getWay(maze, 1, 1)) {
                System.out.println("迷宫可走通");
                maze.printMaze();
            } else {
                System.out.println("迷宫无解");
            }
        }
    }
    
    // 一个迷宫类，规格为m*n
    // 0表示未走过，1表示墙，2表示已走过，3表示不可行
    class Maze {
        public int[][] path;
        public int m, n; //迷宫规格
        public int d1, d2; //迷宫终点
        public Maze(int m, int n, int d1, int d2) {
            this.m = m;
            this.n = n;
            this.d1 = d1;
            this.d2 = d2;
            this.path = new int[m][n];
            // 初始化迷宫
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    path[i][j] = 0;
                }
            }
            // 设置竖边界
            for (int i = 0; i < m; i++) {
                path[i][0] = path[i][n-1] = 1;
            }
    
            // 设置横边界
            for (int j = 0; j < n; j++) {
                path[0][j] = path[m-1][j] = 1;
            }
        }
    
        // 设置墙
        public void setWall(int i, int j) {
            path[i][j] = 1;
        }
        
        // 打印迷宫
        public void printMaze() {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(path[i][j]+" ");
                }
                System.out.println();
            }
        }
    }
    
    /* 输出
    初始化迷宫为
    1 1 1 1 1 1 1 1 
    1 0 1 0 0 0 0 1 
    1 0 1 1 1 0 0 1 
    1 0 0 0 1 0 0 1 
    1 0 1 0 1 0 0 1 
    1 0 1 0 1 1 0 1 
    1 0 1 0 0 0 0 1 
    1 1 1 1 1 1 1 1 
    迷宫可走通
    1 1 1 1 1 1 1 1 
    1 2 1 0 0 0 0 1 
    1 2 1 1 1 0 0 1 
    1 2 2 2 1 0 0 1 
    1 3 1 2 1 0 0 1 
    1 3 1 2 1 1 0 1 
    1 3 1 2 2 2 2 1 
    1 1 1 1 1 1 1 1 
    */