迷宫问题

迷宫找路径问题被广泛应用到生活中。比如游戏,玩过LOL的会发现右下角的地图,其实它就是一个典型的找路径问题。

11074FCB-CF33-4522-AC7C-42C63236C275.jpeg

下面用递归+回溯来说一下,如何找到这条路径。

需求

需求如下图所示,有一个9x9的迷宫,从入口走到出口,如何确定一个有效路径?

9D0658E0-9AD5-4C54-8634-1196CF9F2610.jpeg

思路

1.利用二维数组建立好地图的映射,问题就变成了,从[1,1]走到[8,8]

2.假定:0没走过 1墙 2可以走 3走不通

3.走路遵循 下->右->上->左,即先走下,下走不通走右,右走不通走上,上走不通走左

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
public class Maze { 
private static int HIGH_MAX=10;
private static int WIDTH_MAX=10;

public static void main(String[] args) {

// 先创建一个二维数组,模拟迷宫
// 地图
int[][] map = new int[HIGH_MAX][WIDTH_MAX];

// 初始化所有的墙
init(map);
print(map);

//使用递归回溯给小球找路
setWay(map, 1, 1);
print(map);
}

private static void init(int[][] map){


// 使用 1 表示墙
// 上下全部置为 1
for (int i = 0; i < HIGH_MAX; i++) {
map[0][i] = 1;
map[9][i] = 1;
}
// 左右全部置为 1
for (int i = 0; i < WIDTH_MAX; i++) {
map[i][0] = 1;
map[i][9] = 1;
} //设置挡板, 1 表示
map[1][3] = 1;
map[1][7] = 1;
map[2][3] = 1;
map[2][7] = 1;
map[3][5] = 1;
map[3][6] = 1;
map[4][2] = 1;
map[4][3] = 1;
map[4][4] = 1;
map[5][4] = 1;
map[6][2] = 1;
map[6][6] = 1;
map[7][2] = 1;
map[7][3] = 1;
map[7][4] = 1;
map[7][7] = 1;
map[7][7] = 1;
map[8][1] = 1;

}

private static void print(int[][] map){
// 输出地图
System.out.println("地图的情况");
for (int i = 0; i < WIDTH_MAX; i++) {
for (int j = 0; j < HIGH_MAX; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}

//使用递归回溯来给小球找路
//说明
//1. map 表示地图
//2. i,j 表示从地图的哪个位置开始出发 (1,1)
//3. 如果小球能到 map[WIDTH_MAX-2][HIGH_MAX-2] 位置,则说明通路找到.
//4. 约定: 当 map[i][j] 为 0 表示该点没有走过 当为 1 表示墙; 2 表示通路可以走 ; 3 表示该点已经走过,但是走不通
//5. 在走迷宫时,需要确定一个策略(方法) 下->右->上->左 , 如果该点走不通,再回溯
/**
*
* @param map 表示地图
* @param i 从哪个位置开始找
* @param j
* @return 如果找到通路,就返回 true, 否则返回 false
*/
public static boolean setWay(int[][] map, int i, int j) {
if(map[WIDTH_MAX-2][HIGH_MAX-2] == 2) {
// 通路已经找到 ok
return true;
} else {
if(map[i][j] == 0) {
//如果当前这个点还没有走过
//按照策略 下->右->上->左走
map[i][j] = 2;
// 假定该点是可以走通.
if(setWay(map, i+1, j)) {
//向下走
return true;
} else if (setWay(map, i, j+1)) {
//向右走
return true;
} else if (setWay(map, i-1, j)) {
//向上
return true;
} else if (setWay(map, i, j-1)){
// 向左走
return true;
} else {
//说明该点是走不通,是死路
map[i][j] = 3;
return false;
}
} else {
// 如果 map[i][j] != 0 , 可能是 1, 2, 3
return false;
}
}
}

}

最终结果:

188B5FE3-EBA9-4992-B231-CFE4CD0FB589.jpeg