剑指Offer——回溯算法解迷宫问题（java版）

  以一个M×N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计程序，对任意设定的迷宫，求出从入口到出口的所有通路。
  下面我们来详细讲一下迷宫问题的回溯算法。
(入口) 0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 1 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0(出口)
  该图是一个迷宫的图。1代表是墙不能走，0是可以走的路线。只能往上下左右走，直到从左上角到右下角出口。
  做法是用一个二维数组来定义迷宫的初始状态，然后从左上角开始，不停的去试探所有可行的路线，碰到1就结束本次路径，然后探索其他的方向，当然我们要标记一下已经走的路线，不能反复的在两个可行的格子之间来回走。直到走到出口为止，算找到了一个正确路径。
  程序如下，具体做法看注释即可。

package cn.edu.ujn.demo;

/** 
 * @author SHQ
 * 
 * 迷宫问题求解
 * 
 * 思路
 * 递归+回溯
 * 
 * 按照右-->左-->下-->上的顺序寻路，已走过的路径用5标志
 * 
 * 
 */  
public class MiGong { public static void main(String[] args) { int maxRow,maxLine,p; Scanner in = new Scanner(System.in); Pattern pattern = Pattern.compile("[ ]+"); String s = in.nextLine(); String [] str = pattern.split(s); // 获取行 maxRow = Integer.parseInt(str[0]); // 获取列 maxLine = Integer.parseInt(str[1]); // 获取能量值
// p = Integer.parseInt(str[2]); int [][] array = new int [maxRow][maxLine]; for(int i = 0; i < maxRow; i++){ for(int j = 0; j < maxLine; j++){ array[i][j] = in.nextInt(); } } Long start = System.currentTimeMillis(); new MiGong().check(0, 0, array, maxRow, maxLine); Long end = System.currentTimeMillis(); System.out.println("耗时：" + (end-start) + "ms"); } /** * 制定走的规则 * @param i * @param j * @param array * @param maxRow * @param maxLine */ private void check(int i, int j, int[][] array, int maxRow, int maxLine) { // 递归出口(如果到达右下角出口)   if (i == maxRow - 1 && j == maxLine - 1) { print(array, maxRow, maxLine); return; } //向右走   if (canMove(i, j, i, j + 1, array, maxRow, maxLine)) { // 已走过的点置标志位5 array[i][j] = 5; // 从下一个点继续寻路 check(i, j + 1, array, maxRow, maxLine); // 均不可行，则恢复现场 array[i][j] = 0; } //向左走   if (canMove(i, j, i, j - 1, array, maxRow, maxLine)) { // 标记为已走 array[i][j] = 5; // 递归调用 check(i, j - 1, array, maxRow, maxLine); array[i][j] = 0; } //向下走   if (canMove(i, j, i + 1, j, array, maxRow, maxLine)) { array[i][j] = 5; check(i + 1, j, array, maxRow, maxLine); array[i][j] = 0; } //向上走   if (canMove(i, j, i - 1, j, array, maxRow, maxLine)) { array[i][j] = 5; check(i - 1, j, array,maxRow, maxLine); array[i][j] = 0; } } /** * 判断[i,j]-->[targetI,targetJ]是否可行 * @param i * @param j * @param targetI * @param targetJ * @param array * @param maxRow * @param maxLine * @return boolean 可否通过 */ private boolean canMove(int i, int j, int targetI, int targetJ, int[][] array, int maxRow, int maxLine) {
// System.out.println("从第" + (i + 1) + "行第" + (j + 1) + "列，走到第" + (targetI + 1) + "行第" + (targetJ + 1) + "列");   if (targetI < 0 || targetJ < 0 || targetI >= maxRow || targetJ >= maxLine) {  
// System.out.println("到达最左边或最右边，失败了");   return false; } if (array[targetI][targetJ] == 1) {  
// System.out.println("目标是墙，失败了");   return false; } //避免在两个空格间来回走   if (array[targetI][targetJ] == 5) {
// System.out.println("来回走，失败了");   return false; } return true; } /** * 打印可行路径 * @param array * @param maxRow * @param maxLine */ private void print(int [][] array, int maxRow, int maxLine) { System.out.println("得到一个解："); for (int i = 0; i < maxRow; i++) { for (int j = 0; j < maxLine; j++) { System.out.print(array[i][j] + " "); } System.out.println(); } }  
} 
  

 

  
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
  
115
  
116
  
117
  
118
  
119
  
120
  
121
  
122
  
123
  
124
  
125
  
126
  
127
  
128
  
129
  
130
  
131
 

  计算结果如下：

美文美图

文章来源: shq5785.blog.csdn.net，作者：No Silver Bullet，版权归原作者所有，如需转载，请联系作者。

原文链接：shq5785.blog.csdn.net/article/details/52599850