迷宫问题

img
说明:

  • 小球得到的路径，和程序员 设置的找路策略有关即：找 路的上下左右的顺序相关
  • 再得到小球路径时，可以先 使用(下右上左)，再改成(上 右下左)，看看路径是不是有变化
  • 测试回溯现象
  • 思考: 如何求出最短路径? ``` //下面代码的找路策略是:下右上左 public static boolean setWay(int[][] map, int i, int j) { if (map[6][5] == 2) { // 表示路已经找到了
    1. return true;
    } else {
    1. if (map[i][j] == 0) { // 0: 可以走还没有走
    2.      // 这里开始递归回溯
    3.      map[i][j] = 2; // 认为该点是可以走通,但是不一定
    4.      if (setWay(map, i + 1, j)) { // 下找
    5.         return true;
    6.      } else if (setWay(map, i, j + 1)) { // 右
    7.          return true;
    8.       } else if (setWay(map, i - 1, j)) { // 上
    9.          return true;
    10.       } else if (setWay(map, i, j - 1)) { // 左
    11.          return true;
    12.       } else {// 走不通
    13.          map[i][j] = 3;
    14.          return false;
    15.       }
    16.   } else { 
    17.         //如果map(i)(j)!=0 
    18.          //则值 1,2,3
    19.        return false;}
    }}
  1. ```
  2. int[][] map = new int[8][7];
  3. //上下全部置1
  4. for(int i = 0 ; i<7;i++){
  5.     map[0][i] = 1;
  6.     map[7][i] = 1;
  7. }
  8. //左右全部置1
  9. for (int i = 0; i< 8; i++) {
  10.     map[i][0] = 1;
  11.     map[i][6] = 1;
  12. }

完整代码

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

运行结果

  1. 地图的情况
  2. 1 1 1 1 1 1 1 
  3. 1 0 0 0 0 0 1 
  4. 1 0 0 0 0 0 1 
  5. 1 1 1 0 0 0 1 
  6. 1 0 0 0 0 0 1 
  7. 1 0 0 0 0 0 1 
  8. 1 0 0 0 0 0 1 
  9. 1 1 1 1 1 1 1 
  10. 小球走过，并标识过的 地图的情况
  11. 1 1 1 1 1 1 1 
  12. 1 2 2 2 2 2 1 
  13. 1 0 0 0 0 2 1 
  14. 1 1 1 0 0 2 1 
  15. 1 0 0 0 0 2 1 
  16. 1 0 0 0 0 2 1 
  17. 1 0 0 0 0 2 1 
  18. 1 1 1 1 1 1 1 
  20. Process finished with exit code 0

通过递归,遍历所有方式的路径,共享棋盘中的数组位置数据

实现查找最优解

策略:下->右->上->左

最后噼里啪啦的回去了

回溯