本文为大家分享了使用栈的迷宫算法java版，主要考察栈的使用，供大家参考，具体内容如下
主要思路如下：
|
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
|
do {
if(当前位置可通过) {
标记此位置已走过;
保存当前位置并入栈;
if(当前位置为终点) {
程序结束;
}
获取下一个位置;
}
else {
if(栈非空) {
出栈；
while(当前位置方向为4且栈非空) {
标记当前位置不可走;
出栈;
}
if(当前位置的方向小于4) {
方向+1;
重新入栈;
获取下一个位置;
}
}
}
}
while (栈非空);
|
java代码如下：
|
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
|
import java.util.Stack;
public class Maze {
// 栈
private Stack<MazeNode> stack = new Stack<Maze.MazeNode>();
// 迷宫
private int[][] maze = {
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},
{1,0,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},
{1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},
{1,1,1,0,0,1,1,1,1,1,1,0,1,1,0,0,1},
{1,1,0,0,1,0,0,1,0,1,1,1,1,1,1,1,1},
{1,0,0,1,1,1,1,1,1,0,1,0,0,1,0,1,1},
{1,0,0,1,1,1,1,1,1,0,1,0,0,1,0,1,1},
{1,0,1,1,1,0,0,0,0,1,1,1,1,1,1,1,1},
{1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1},
{1,1,0,0,0,0,1,1,0,1,0,0,0,0,0,0,1},
{1,1,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},
{1,0,0,0,0,1,1,1,1,1,0,1,1,1,1,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
};
// 标记路径是否已走过
private int[][] mark = new int[MAZE_SIZE_X][MAZE_SIZE_Y];
private static final int MAZE_SIZE_X = 14;
private static final int MAZE_SIZE_Y = 17;
private static final int END_X = 12;
private static final int END_Y = 15;
private void initMark() {
for (int i = 0; i < MAZE_SIZE_X; i++) {
for (int j = 0; j < MAZE_SIZE_Y; j++) {
mark[i][j] = 0;
}
}
}
public void process() {
initMark();
Position curPos = new Position(1, 1);
do {
// 此路径可走
if (maze[curPos.x][curPos.y] == 0 && mark[curPos.x][curPos.y] == 0) {
mark[curPos.x][curPos.y] = 1;
stack.push(new MazeNode(curPos, 1));
// 已到终点
if (curPos.x == END_X && curPos.y == END_Y) {
return;
}
curPos = nextPos(curPos, stack.peek().direction);
}
// 走不通
else {
if (!stack.isEmpty()) {
MazeNode curNode = stack.pop();
while (curNode.direction == 4 && !stack.isEmpty()) {
// 如果当前位置的4个方向都已试过，那么标记该位置不可走，并出栈
mark[curNode.position.x][curNode.position.y] = 1;
curNode = stack.pop();
}
if (curNode.direction < 4) {
curNode.direction++;// 方向+1
stack.push(curNode);// 重新入栈
curPos = nextPos(curNode.position, curNode.direction);// 获取下一个位置
}
}
}
}
while(!stack.isEmpty());
}
public void drawMaze() {
for (int i = 0; i < maze.length; i++) {
for (int j = 0; j < maze[0].length; j++) {
System.out.print(maze[i][j]);
}
System.out.print("\n");
}
System.out.print("\n");
}
public void drawResult() {
initMark();
MazeNode node;
while (!stack.isEmpty()) {
node = stack.pop();
mark[node.position.x][node.position.y] = 1;
}
for (int i = 0; i < mark.length; i++) {
for (int j = 0; j < mark[0].length; j++) {
System.out.print(mark[i][j]);
}
System.out.print("\n");
}
System.out.print("\n");
}
// 记录迷宫中的点的位置
class Position {
int x;
int y;
public Position(int x, int y) {
this.x = x;
this.y = y;
}
}
// 栈中的结点
class MazeNode {
Position position;
int direction;
public MazeNode(Position pos) {
this.position = pos;
}
public MazeNode(Position pos, int dir) {
this.position = pos;
this.direction = dir;
}
}
// 下一个位置，从右开始，顺时针
public Position nextPos(Position position, int direction) {
Position newPosition = new Position(position.x, position.y);
switch (direction) {
case 1:
newPosition.y += 1;
break;
case 2:
newPosition.x += 1;
break;
case 3:
newPosition.y -= 1;
break;
case 4:
newPosition.x -= 1;
break;
default:
break;
}
return newPosition;
}
public static void main(String[] args) {
Maze maze = new Maze();
maze.drawMaze();
maze.process();
maze.drawResult();
}
}
|
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：http://blog.csdn.net/Young_Leez/article/details/44026295