迷宫回溯问题

概念介绍

　　有同学想了解迷宫回溯问题，今天它来了！不啰嗦，直接上需求！　　

　　请看图，上图为一个迷宫，1为阻挡区间，也就是说不能走。0为可踏足地带，我们的目标是从A点出发，走到B点，则任务完成！

　　为了方便大家理解，我们只在（3,1）以及（3,2）这两个位置设置阻挡位。

代码实现

　　先明确实现思路：假设我们在A（1,1）位置，我们能做的操作是尝试向下、向右、向上或者向左走一步。假设我们向下走一步成功后，到达（2,1）的位置，我们能做的操作就是重复在A点的操作。既然每一步的操作相同，只不过结果可能不同，那么这时候我们可以使用递归的思想！当我们用到递归时，一定要注意，退出递归的条件，那就是B（6,5）被标记为已经走过，在这里，我们约定，走过的点会被标记为2。不啰嗦，开始写代码。

　　第一步:构造图上的迷宫。

 1  public static int[][] buildMap(){
 2         // 使用二维数组模拟迷宫
 3         int[][] map = new int[8][7];
 4         // 使用1表示墙，上下全部置为1
 5         for (int i = 0; i < 7; i++) {
 6             map[0][i] = 1;
 7             map[7][i] = 1;
 8         }
 9         for (int i = 0; i < 8; i++) {
10             map[i][0] = 1;
11             map[i][6] = 1;
12         }
13         // 设置挡板
14         map[3][1] = 1;
15         map[3][2] = 1;
16         return map;
17     }

　　第二步：实现行走迷宫的方法。

　　在这里，我们规定：1表示墙，2表示走过路，3表示该点为死胡同，已经踏足，但是走不通了。

　　我们设置的地图很简单，所以不会出现死胡同的情况，大家可以设计迷宫复杂一些，就会出现死胡同的情况。

　　2.1 定义咱们的方法

1  /**
2      * @param map 表示地图
3      * @param i,j 表示起始位置
4      * @return 如果能接着往下走，就返回true, 否则返回false
5      */
6     public static boolean walk(int[][] map, int i, int j){
7     }

　　2.2 当我们即将踏足点A，需要做两件事，一件事是A点我们没有走过，另一件是我们踏足后，标记该点为已经走过

 1  /**
 2      * @param map 表示地图
 3      * @param i,j 表示起始位置
 4      * @return 如果能接着往下走，就返回true, 否则返回false
 5      */
 6     public static boolean walk(int[][] map, int i, int j){11         // 先保障我们所在点位上是我们没有走过的点
12         if(map[i][j] == 0) {
13            // 当我们踏足这个点的瞬间，标记该点位为2，说明改点我们已经走过
14            map[i][j] = 2;32         }
33     }

　　2.3 执行我们行走策略，执行策略可以有很多种，比如右→下→左→上或者下→右→上→左等，这里我们使用下→右→上→左

 1                 // 执行我们走迷宫的策略：下→右→上→左
 2                 if(walk(map, i+1, j)) { //向下
 3                     return true;
 4                 } else if (walk(map, i, j+1)) { //向右
 5                     return true;
 6                 } else if (walk(map, i-1, j)) { //向上
 7                     return true;
 8                 } else if (walk(map, i, j-1)){ // 向左
 9                     return true;
10                 } else {
11                     // 当所有策略都走不通的情况下，说明该路为死路
12                     map[i][j] = 3;
13                     return false;
14                 }

　　2.4设置行走结束条件，走到B点：map[6][5] == 2

 1  /**
 2      * @param map 表示地图
 3      * @param i,j 表示起始位置
 4      * @return 如果能接着往下走，就返回true, 否则返回false
 5      */
 6     public static boolean walk(int[][] map, int i, int j){
 7         // 已经走到目标点位
 8         if(map[6][5] == 2) {
 9             return true;
10         } else {
11             // 先保障我们所在点位上是我们没有走过的点
12             if(map[i][j] == 0) {
13                 // 当我们踏足这个点的瞬间，标记该点位为2，说明改点我们已经走过
14                 map[i][j] = 2;
15                 // 执行我们走迷宫的策略：下→右→上→左
16                 if(walk(map, i+1, j)) { //向下
17                     return true;
18                 } else if (walk(map, i, j+1)) { //向右
19                     return true;
20                 } else if (walk(map, i-1, j)) { //向上
21                     return true;
22                 } else if (walk(map, i, j-1)){ // 向左
23                     return true;
24                 } else {
25                     // 当所有策略都走不通的情况下，说明该路为死路
26                     map[i][j] = 3;
27                     return false;
28                 }
29             } else {
30                 return false;
31             }
32         }
33     }

　　至此，代码编写完成，Git地址：https://github.com/HollowCup/algorithms-and-data-structure，具体实现位于algorithm工程下的map目录，如果发现不足之处，请联系我进行更改，十分感谢！关注我，带你了解更多算法！