Java假定用二维数组表示迷宫,墙用1表示,通路用0表示。迷宫的左上角为起点,假设坐标(1,1),迷宫的终点右下角,坐标为(8,8)。请使用栈,找出一条从起点到终点的走迷宫路线并输出此路线上每个点的坐标。
时间: 2024-12-23 21:21:46 浏览: 3
在Java中,可以使用深度优先搜索(DFS)算法结合栈来解决这个问题。以下是使用二维数组和栈实现的一种解决方案:
```java
import java.util.ArrayList;
import java.util.List;
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "(" + x + ", " + y + ")";
}
}
public class MazeSolver {
private static final int[][] MAZE = {{0, 0, 1, 1, 0, 0},
{0, 0, 0, 0, 1, 0},
{1, 1, 0, 0, 1, 1},
{1, 1, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0}};
public static List<Point> findPath(int startX, int startY, int endX, int endY) {
List<Point> path = new ArrayList<>();
Stack<Point> stack = new Stack<>();
stack.push(new Point(startX, startY));
path.add(new Point(startX, startY));
while (!stack.isEmpty()) {
Point current = stack.pop();
// 检查当前位置是否是终点
if (current.x == endX && current.y == endY) {
break;
}
// 邻居遍历,将可达的非墙位置压入栈
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
int nx = current.x + dx;
int ny = current.y + dy;
// 只有当移动到的坐标在合法范围内,并且不是墙的位置才继续
if (nx >= 0 && nx < MAZE.length && ny >= 0 && ny < MAZE[0].length && MAZE[nx][ny] == 0) {
stack.push(new Point(nx, ny));
path.add(new Point(nx, ny));
}
}
}
}
return path;
}
public static void main(String[] args) {
List<Point> path = findPath(1, 1, 8, 8);
if (path.isEmpty()) {
System.out.println("无法从起点到达终点");
} else {
for (Point point : path) {
System.out.println(point);
}
}
}
}
```
这个程序首先初始化一个起点(1,1),并将它放入栈中。然后不断弹出栈顶元素,检查其是否为目标点,如果不是,则遍历所有相邻的点(上下左右)。如果是非墙位置并且未访问过,将其加入路径列表并压入栈。最后,返回找到的路径。
注意,如果没有找到路径,`findPath`方法会返回一个空列表。在`main`函数中,我们打印路径中的每个点。
阅读全文