image.png

    1. package com.atguigu.recursion;
    3. /**
    4.  * 迷宫问题
    5.  * @author Dxkstart
    6.  * @create 2021-10-09-11:17
    7.  */
    8. public class MiGong {
    9.     public static void main(String[] args) {
    10.         //先创建一个二维数组，模拟迷宫
    11.         //地图
    12.         int[][] map = new int[8][7];
    13.         //将迷宫的上下行置为1，模拟墙
    14.         for (int i = 0; i < 7; i++) {
    15.             map[0][i] = 1;
    16.             map[7][i] = 1;
    17.         }
    18.         //将迷宫的左右列置为1，模拟墙
    19.         for (int i = 0; i < 8; i++) {
    20.             map[i][0] = 1;
    21.             map[i][6] = 1;
    22.         }
    23.         //地图中的其余的墙
    24.         map[3][1] = 1;
    25.         map[3][2] = 1;
    28.         //输出地图
    29.         System.out.println("地图的情况为:");
    30.         for (int i = 0; i < 8; i++) {
    31.             for (int j = 0; j < 7; j++) {
    32.                 System.out.print(map[i][j] + " ");
    33.             }
    34.             System.out.println();
    36.         }
    38.         //使用递归回溯给小球找路
    39.         setWay(map,1,1);
    41.         //输出新的地图，小球走过，并标识过的递归
    42.         System.out.println("新地图的情况为:");
    43.         for (int i = 0; i < 8; i++) {
    44.             for (int j = 0; j < 7; j++) {
    45.                 System.out.print(map[i][j] + " ");
    46.             }
    47.             System.out.println();
    49.         }
    50.     }
    52.     //使用递归回溯来给小球找路
    54.     //1.map表示地图
    55.     //2.i,j 表示从地图的那个位置开始出发(1,1)
    56.     //3.如果小球能到map[6][5]位置，则说明通路找到
    57.     //4.约定：当map[i][j] 为0表示该点没有走过，当为1表示为墙，2表示通路可以走，3表示该点已经走过，但是走不通
    58.     //5.在走迷宫时，需要确定一个策略(方法)，下->右->上->左，如果该点走不通，再回溯
    59.     /**
    60.      *
    61.      * @param map 表示地图
    62.      * @param i 从哪个位置开始找
    63.      * @param j
    64.      * @return 如果找打通路，返回true，否则返回false
    65.      */
    66.     public static boolean setWay(int[][] map,int i,int j){
    67.         if (map[6][5] == 2){//通路已经找到，ok了
    68.             return true;
    69.         }else {
    70.             if (map[i][j] == 0){//如果当前这个点还没有走过
    71.                 //按照策略 下->右->上->左 走
    72.                 map[i][j] = 2;//假定该点是可以走通的
    73.                 if (setWay(map, i+1, j)){//向下走
    74.                     return true;
    75.                 }else if (setWay(map, i, j+1)){//向右走
    76.                     return true;
    77.                 }else if (setWay(map, i-1, j)){//向上走
    78.                     return true;
    79.                 }else if (setWay(map, i, j-1)){//向左走
    80.                     return true;
    81.                 }else {
    82.                     //说明该点是死路，走不通
    83.                     map[i][j] = 3;
    84.                     return false;
    85.                 }
    86.             }else {//如果map[i][j] != 0,可能是1,2,3
    87.                 return false;
    88.             }
    89.         }
    90.     }
    91. }

    image.png