概述
以一个M×N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。
解题思路
可使用回溯方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。
探索迷宫的四个方向：RIGHT为向右，DOWN向下，LEFT向左，UP向上，输出从入口到出口的行走路径。
程序代码
代码1
代码：采用循环方式，进行回溯计算。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23package demo2;
/**
* 位置
*
* @author Administrator
*/
class Position {
int row;// 行
int col;// 列
public Position() {
}
public Position(int row, int col) {
this.col = col;
this.row = row;
}
public String toString() {
return "(" + row + " ," + col + ")";
}
}
迷宫代码主类: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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159package demo2;
import java.util.Stack;
/**
* 回溯方法-解题迷宫
*/
class Maze {
//迷宫地图
int[][] maze = {{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}};
private int row = 9;
private int col = 8;
//存储迷宫路线
Stack<Position> stack;
//坐标点的是否通路
//true：通路，false：不通
boolean p[][] = null;
public Maze() {
//maze = new int[15][15];
stack = new Stack<Position>();
p = new boolean[15][15];
}
/*
* 构造迷宫
*/
public void init() {
/*Scanner scanner = new Scanner(System.in);
System.out.println("请输入迷宫的行数");
row = scanner.nextInt();
System.out.println("请输入迷宫的列数");
col = scanner.nextInt();
*/
//System.out.println("请输入" + row + "行" + col + "列的迷宫");
//int temp = 0;
//初始化路线都不通
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
//temp = scanner.nextInt();
//maze[i][j] = temp;
p[i][j] = false;
}
}
}
/*
* 回溯迷宫，查看是否有出路
*
* 1：围墙
* 0：通的路
*/
public void findPath() {
// 给原始迷宫的周围家一圈围墙
int[][] temp = new int[row + 2][col + 2];
for (int i = 0; i < row + 2; ++i) {
for (int j = 0; j < col + 2; ++j) {
//第一行
temp[0][j] = 1;
//最后一行
temp[row + 1][j] = 1;
//第一列，最后一列
temp[i][0] = temp[i][col + 1] = 1;
}
}
// 将原始迷宫复制到新的迷宫中
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
temp[i + 1][j + 1] = maze[i][j];
}
}
// 从左上角开始按照顺时针开始查询
int i = 1;
int j = 1;
//第1个点被访问
p[i][j] = true;
//存储迷宫路线
stack.push(new Position(i, j));
//探索迷宫的四个方向：向右，向下，向左，向上，输出从入口到出口的行走路径。
while (!stack.empty() && (!(i == (row) && (j == col)))) {
//列右
if ((temp[i][j + 1] == 0) && (p[i][j + 1] == false)) {
p[i][j + 1] = true;
stack.push(new Position(i, j + 1));
j++;
} else if ((temp[i + 1][j] == 0) && (p[i + 1][j] == false)) {//行右
p[i + 1][j] = true;
stack.push(new Position(i + 1, j));
i++;
} else if ((temp[i][j - 1] == 0) && (p[i][j - 1] == false)) {//列左
p[i][j - 1] = true;
stack.push(new Position(i, j - 1));
j--;
} else if ((temp[i - 1][j] == 0) && (p[i - 1][j] == false)) {//行左
p[i - 1][j] = true;
stack.push(new Position(i - 1, j));
i--;
} else {
//删除栈顶部元素
stack.pop();
//没有路线，退出循环
if (stack.empty()) {
break;
}
//获取栈顶行值
i = stack.peek().row;
//获取栈顶列值
j = stack.peek().col;
}
}
//存储新位置
Stack<Position> newPos = new Stack<Position>();
if (stack.empty()) {
System.out.println("没有路径");
} else {
System.out.println("有路径");
System.out.println("路径如下：");
while (!stack.empty()) {
Position pos = new Position();
pos = stack.pop();
newPos.push(pos);
}
}
/*
* 图形化输出路径
*/
String resault[][] = new String[row + 1][col + 1];
for (int k = 0; k < row; ++k) {
for (int t = 0; t < col; ++t) {
resault[k][t] = (maze[k][t]) + "";
}
}
//迷宫路线值
while (!newPos.empty()) {
Position p1 = newPos.pop();
resault[p1.row - 1][p1.col - 1] = "#";
}
//打印迷宫数据
for (int k = 0; k < row; ++k) {
for (int t = 0; t < col; ++t) {
System.out.print(resault[k][t] + "\t");
}
System.out.println();
}
}
}
1 | package demo2; |
结果:1
2
3
4
5
6
7
8
9
10
11
12有路径
路径如下：
# # 1 0 0 0 1 0
0 # 1 0 0 0 1 0
# # 1 0 1 1 0 1
# 1 1 1 0 0 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
耗时【0豪秒】 .............................
代码2
代码：经典的回溯算法，此代码采用递归的方式，每当执行1次打印迷宫日志完，会回到上1次递归处，继续执行判断。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
115package demo3;
/**
*回溯方法-解题迷宫2
*/
public class MiGong {
/**
* 定义迷宫数组
*/
private int[][] array = {
{ 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 } };
private int maxLine = 8;
private int maxRow = 9;
public static void main(String[] args) {
long s1 = System.currentTimeMillis();
new MiGong().check(0, 0);
long s2 = System.currentTimeMillis();
System.out.println("耗时【" + (s2 - s1) + "豪秒】 .............................");
}
/**
*
* @param i
* 行
* @param j
* 列
*/
private void check(int i, int j) {
// 如果到达右下角出口
// 循环到最后一行
if (i == maxRow - 1 && j == maxLine - 1) {
//打印
print();
return;
}
// 向右走
//同行，列+1
if (canMove(i, j, i, j + 1)) {
//标记当前位置已经走过
array[i][j] = 5;
check(i, j + 1);
//位置不通
array[i][j] = 0;
}
// 向左走
//同行，列-1
if (canMove(i, j, i, j - 1)) {
array[i][j] = 5;
check(i, j - 1);
array[i][j] = 0;
}
// 向下走
//同列，行+1
if (canMove(i, j, i + 1, j)) {
array[i][j] = 5;
check(i + 1, j);
array[i][j] = 0;
}
// 向上走
//同行，列-1
if (canMove(i, j, i - 1, j)) {
array[i][j] = 5;
check(i - 1, j);
array[i][j] = 0;
}
}
/**
*
* @param i 当前行
* @param j 当前列
* @param targetI 下一行
* @param targetJ 下一列
* @return
*/
private boolean canMove(int i, int j, int targetI, int targetJ) {
// 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;
}
private void print() {
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得到一个解：
5 5 1 0 0 0 1 0
5 5 1 0 0 0 1 0
5 0 1 0 1 1 0 1
5 1 1 1 0 0 1 0
5 5 5 1 5 5 5 0
0 1 5 5 5 1 5 1
0 1 1 1 1 0 5 1
1 1 0 0 0 1 5 1
1 1 0 0 0 0 5 0
得到一个解：
5 5 1 0 0 0 1 0
5 5 1 0 0 0 1 0
5 0 1 0 1 1 0 1
5 1 1 1 5 5 1 0
5 5 5 1 5 5 5 0
0 1 5 5 5 1 5 1
0 1 1 1 1 0 5 1
1 1 0 0 0 1 5 1
1 1 0 0 0 0 5 0
得到一个解：
5 5 1 0 0 0 1 0
0 5 1 0 0 0 1 0
5 5 1 0 1 1 0 1
5 1 1 1 0 0 1 0
5 5 5 1 5 5 5 0
0 1 5 5 5 1 5 1
0 1 1 1 1 0 5 1
1 1 0 0 0 1 5 1
1 1 0 0 0 0 5 0
得到一个解：
5 5 1 0 0 0 1 0
0 5 1 0 0 0 1 0
5 5 1 0 1 1 0 1
5 1 1 1 5 5 1 0
5 5 5 1 5 5 5 0
0 1 5 5 5 1 5 1
0 1 1 1 1 0 5 1
1 1 0 0 0 1 5 1
1 1 0 0 0 0 5 0
得到一个解：
5 0 1 0 0 0 1 0
5 5 1 0 0 0 1 0
5 5 1 0 1 1 0 1
5 1 1 1 0 0 1 0
5 5 5 1 5 5 5 0
0 1 5 5 5 1 5 1
0 1 1 1 1 0 5 1
1 1 0 0 0 1 5 1
1 1 0 0 0 0 5 0
得到一个解：
5 0 1 0 0 0 1 0
5 5 1 0 0 0 1 0
5 5 1 0 1 1 0 1
5 1 1 1 5 5 1 0
5 5 5 1 5 5 5 0
0 1 5 5 5 1 5 1
0 1 1 1 1 0 5 1
1 1 0 0 0 1 5 1
1 1 0 0 0 0 5 0
得到一个解：
5 0 1 0 0 0 1 0
5 0 1 0 0 0 1 0
5 0 1 0 1 1 0 1
5 1 1 1 0 0 1 0
5 5 5 1 5 5 5 0
0 1 5 5 5 1 5 1
0 1 1 1 1 0 5 1
1 1 0 0 0 1 5 1
1 1 0 0 0 0 5 0
得到一个解：
5 0 1 0 0 0 1 0
5 0 1 0 0 0 1 0
5 0 1 0 1 1 0 1
5 1 1 1 5 5 1 0
5 5 5 1 5 5 5 0
0 1 5 5 5 1 5 1
0 1 1 1 1 0 5 1
1 1 0 0 0 1 5 1
1 1 0 0 0 0 5 0
耗时【5豪秒】 .............................
