迷宫回溯问题分析

问题：

迷宫为8x8的二位数组，其中0为道路，1为墙，人如何在起点和终点之前获取一条可达路径。

 自定义的概念： 

当前位置：人当前所在的位置，通过当前位置不断变动形成一条路径。

策略：人站在当前位置上，向哪个方向来前进到下一个位置，以及如果下一个位置不可到达终点，那么换哪个方向继续前进（例：下->右->上->左）。

分析：

以当前位置为起始位置，然后根据策略前进到下一个位置，通过递归一直前进下去。如果不通则换一个方向继续前进。

如果前后左右都不通（前后左右的位置为墙、走过的位置、死胡同），那么当前位置为死胡同，设为3。回溯到前一个位置继续前进，直到找到出口。

代码：

  1 public class LabyrinthRetrospectiveTest {
  2     public static void main(String[] args) {
  3         LabyrinthRetrospective labyrinthRetrospective = new LabyrinthRetrospective();
  4         labyrinthRetrospective.createMap();
  5         labyrinthRetrospective.showMap();
  6         System.out.println("~~~~~开始前行~~~~~");
  7         labyrinthRetrospective.exploreWay(1, 1, 6, 6);
  8         labyrinthRetrospective.showMap();
  9     }
 10 }
 11 
 12 /**
 13  * 迷宫回溯
 14  */
 15 class LabyrinthRetrospective {
 16 
 17     /**
 18      * 迷宫地图
 19      */
 20     private int[][] map;
 21 
 22     /**
 23      * 迷宫的道路
 24      */
 25     public static final int ROAD = 0;
 26 
 27     /**
 28      * 迷宫的墙
 29      */
 30     public static final int WALL = 1;
 31 
 32     /**
 33      * 行进的轨迹
 34      */
 35     public static final int TRACK = 2;
 36 
 37     /**
 38      * 死胡同
 39      */
 40     public static final int BLIND_ALLEY = 3;
 41 
 42     /**
 43      * 创建地图
 44      * @return
 45      */
 46     public void createMap() {
 47         map = new int[8][8];
 48         for (int i = 0; i < 8; i++) {
 49             map[0][i] = WALL;
 50             map[7][i] = WALL;
 51             map[i][0] = WALL;
 52             map[i][7] = WALL;
 53         }
 54         map[2][2] = WALL;
 55         map[3][2] = WALL;
 56         map[4][2] = WALL;
 57         map[5][2] = WALL;
 58         map[5][1] = WALL;
 59         map[4][3] = WALL;
 60         map[4][4] = WALL;
 61         map[4][6] = WALL;
 62     }
 63 
 64     /**
 65      * 显示地图
 66      */
 67     public void showMap() {
 68         System.out.println("~~~~~迷宫的地图~~~~~");
 69         for (int i = 0; i < map.length; i++) {
 70             for (int j = 0; j < map[i].length; j++) {
 71                 System.out.printf("%d\t", map[i][j]);
 72             }
 73             System.out.println();
 74         }
 75     }
 76 
 77     /**
 78      * 迷宫前行
 79      * @param startLine   起始位置的行下标
 80      * @param startColumn 起始位置的列下标
 81      * @param endLine     终止位置的行下标
 82      * @param endColumn   终止位置的列下标
 83      * @return            是否可通向终点
 84      */
 85     public boolean exploreWay(int startLine, int startColumn, int endLine, int endColumn) {
 86         if (map[endLine][endColumn] == TRACK) {
 87             //到达终点
 88             return true;
 89         }
 90 
 91         if (map[startLine][startColumn] == ROAD) {
 92             //可以前进
 93             map[startLine][startColumn] = TRACK;
 94             //以当前位置为起点，继续前进，前进策略为下->右->上->左
 95             if (exploreWay(startLine + 1, startColumn, endLine, endColumn)) {
 96                 //策略可行
 97                 return true;
 98             } else if (exploreWay(startLine, startColumn + 1, endLine, endColumn)) {
 99                 //策略可行
100                 return true;
101             } else if (exploreWay(startLine - 1, startColumn, endLine, endColumn)) {
102                 //策略可行
103                 return true;
104             } else if (exploreWay(startLine, startColumn - 1, endLine, endColumn)) {
105                 //策略可行
106                 return true;
107             } else {
108                 //走到死胡同
109                 map[startLine][startColumn] = BLIND_ALLEY;
110                 return false;
111             }
112         } else {
113             //此路不通
114             return false;
115         }
116     }
117 }

结果：