zcq

    1. package com.atguigu.recursion;
    3. public class MiGong {
    5.     public static void main(String[] args) {
    6.         // 先创建一个二维数组，模拟迷宫
    7.         // 地图
    8.         int[][] map = new int[8][7];
    9.         // 使用1 表示墙
    10.         // 上下全部置为1
    11.         for (int i = 0; i < 7; i++) {
    12.             map[0][i] = 1;
    13.             map[7][i] = 1;
    14.         }
    16.         // 左右全部置为1
    17.         for (int i = 0; i < 8; i++) {
    18.             map[i][0] = 1;
    19.             map[i][6] = 1;
    20.         }
    21.         //设置挡板, 1 表示
    22.         map[3][1] = 1;
    23.         map[3][2] = 1;
    24. //        map[1][2] = 1;
    25. //        map[2][2] = 1;
    27.         // 输出地图
    28.         System.out.println("地图的情况");
    29.         for (int i = 0; i < 8; i++) {
    30.             for (int j = 0; j < 7; j++) {
    31.                 System.out.print(map[i][j] + " ");
    32.             }
    33.             System.out.println();
    34.         }
    36.         //使用递归回溯给小球找路
    37.         //setWay(map, 1, 1);
    38.         setWay2(map, 1, 1);
    40.         //输出新的地图, 小球走过，并标识过的递归
    41.         System.out.println("小球走过，并标识过的 地图的情况");
    42.         for (int i = 0; i < 8; i++) {
    43.             for (int j = 0; j < 7; j++) {
    44.                 System.out.print(map[i][j] + " ");
    45.             }
    46.             System.out.println();
    47.         }
    49.     }
    51.     //使用递归回溯来给小球找路
    52.     //说明
    53.     //1. map 表示地图
    54.     //2. i,j 表示从地图的哪个位置开始出发 (1,1)
    55.     //3. 如果小球能到 map[6][5] 位置，则说明通路找到.
    56.     //4. 约定： 当map[i][j] 为 0 表示该点没有走过 当为 1 表示墙  ； 2 表示通路可以走 ； 3 表示该点已经走过，但是走不通
    57.     //5. 在走迷宫时，需要确定一个策略(方法) 下->右->上->左 , 如果该点走不通，再回溯
    58.     /**
    59.      * 
    60.      * @param map 表示地图
    61.      * @param i 从哪个位置开始找
    62.      * @param j 
    63.      * @return 如果找到通路，就返回true, 否则返回false
    64.      */
    65.     public static boolean setWay(int[][] map, int i, int j) {
    66.         if(map[6][5] == 2) { // 通路已经找到ok
    67.             return true;
    68.         } else {
    69.             if(map[i][j] == 0) { //如果当前这个点还没有走过
    70.                 //按照策略 下->右->上->左  走
    71.                 map[i][j] = 2; // 假定该点是可以走通.
    72.                 if(setWay(map, i+1, j)) {//向下走
    73.                     return true;
    74.                 } else if (setWay(map, i, j+1)) { //向右走
    75.                     return true;
    76.                 } else if (setWay(map, i-1, j)) { //向上
    77.                     return true;
    78.                 } else if (setWay(map, i, j-1)){ // 向左走
    79.                     return true;
    80.                 } else {
    81.                     //说明该点是走不通，是死路
    82.                     map[i][j] = 3;
    83.                     return false;
    84.                 }
    85.             } else { // 如果map[i][j] != 0 , 可能是 1， 2， 3
    86.                 return false;
    87.             }
    88.         }
    89.     }
    91.     //修改找路的策略，改成 上->右->下->左
    92.     public static boolean setWay2(int[][] map, int i, int j) {
    93.         if(map[6][5] == 2) { // 通路已经找到ok
    94.             return true;
    95.         } else {
    96.             if(map[i][j] == 0) { //如果当前这个点还没有走过
    97.                 //按照策略 上->右->下->左
    98.                 map[i][j] = 2; // 假定该点是可以走通.
    99.                 if(setWay2(map, i-1, j)) {//向上走
    100.                     return true;
    101.                 } else if (setWay2(map, i, j+1)) { //向右走
    102.                     return true;
    103.                 } else if (setWay2(map, i+1, j)) { //向下
    104.                     return true;
    105.                 } else if (setWay2(map, i, j-1)){ // 向左走
    106.                     return true;
    107.                 } else {
    108.                     //说明该点是走不通，是死路
    109.                     map[i][j] = 3;
    110.                     return false;
    111.                 }
    112.             } else { // 如果map[i][j] != 0 , 可能是 1， 2， 3
    113.                 return false;
    114.             }
    115.         }
    116.     }
    118. }