递归求解迷宫问题

╰+哭是因爲堅強的太久メ 2023-07-08 02:42 26阅读 0赞

package com.yg.recursion;/*
    @author  GeQiLin
    @date    2020/2/24  16:01
    */
    
    public class MiGong {
        private static int col = 7;
        private static int row = 6;
        private static int[][] map;//用二维数组模拟迷宫
    
        public static void main(String[] args) {
            map = setMapUI(col, row);
            printMapUI(map);
            //设置起点
            setWay(map, 1, 1);
            System.out.println("路径为：");
            printMapUI(map);
        }
    
        //用递归求迷宫路径
        private static boolean setWay(int[][] map, int i, int j) {
            //设置迷宫终点
            if (map[col - 2][row - 2] == 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 {
                    //map[i][j]!=0，则表示它等于1，2，3，的一种
                    return false;
                }
            }
        }
    
        //打印迷宫
        private static void printMapUI(int[][] map) {
            for (int i = 0; i < map.length; i++) {
                for (int j = 0; j < map[0].length; j++) {
                    System.out.printf(map[i][j] + " ");
                }
                System.out.println();
            }
        }
    
        /*
         * 构造迷宫
         * map[i][j]
         * 为0则表示没有走过，
         * 为1则表示是围墙。
         * 为2则表示能走通，
         * 为3表示走不通
         * */
    
        private static int[][] setMapUI(int col, int row) {
            int[][] map = new int[col][row];
            //构造迷宫上下边界
            for (int i = 0; i < row; i++) {
                map[0][i] = 1;
                map[col - 1][i] = 1;
            }
            //构造迷宫左右边界
            for (int j = 0; j < col; j++) {
                map[j][0] = 1;
                map[j][row - 1] = 1;
            }
            //设置挡板
            map[3][1] = 1;
            map[3][2] = 1;
            return map;
        }
    }