用java语言以一个 m * n 的长方阵表示迷宫, 0和1分别表示迷宫的通路和障碍。 设计一个程序, 对任意设定的迷宫, 求出一条从入口到出口的通路, 或得出没有通路的结论。 基本要求 : (1) 实现一个以链表做存储的栈类型, 然后编写一个求解迷宫的非递归程序。 求的通路以三元组(i, j, d) 的形式输出, 其中:(i, j) 指示迷宫中的一个坐标, d 表示走到下一坐标的方向。 如: 对于下列数据的迷宫, 输出一条通路: (1, 1, 1),(1, 2, 2), (2, 2, 2),(3, 2, 3),(3, 1, 2) ……。 (2) 编写递归形式的算法, 求得迷宫中所有可能的道路;
时间: 2023-06-26 12:08:16 浏览: 41
1. 非递归形式的求解迷宫程序
我们可以使用栈来模拟深度优先搜索(DFS)的过程,从起点开始,每次将当前位置入栈,并标记为已访问,然后按照顺时针方向依次探索相邻位置,如果找到终点,则输出路径,并结束搜索;否则如果找到了未访问的相邻位置,则将其入栈,继续搜索;如果所有相邻位置都已经访问过,则将当前位置出栈,回溯到上一层。
具体实现可以参考下面的代码:
```java
import java.util.*;
// 定义迷宫节点类
class MazeNode {
public int x, y; // 节点坐标
public int dir; // 方向,1-4 表示上下左右
public MazeNode(int x, int y, int dir) {
this.x = x;
this.y = y;
this.dir = dir;
}
}
// 定义迷宫类
class Maze {
private int[][] maze; // 迷宫数组
private int m, n; // 迷宫的行数和列数
private boolean[][] visited; // 标记节点是否已经访问过
private int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向
public Maze(int[][] maze) {
this.maze = maze;
this.m = maze.length;
this.n = maze[0].length;
this.visited = new boolean[m][n];
}
// 检查一个节点是否可以访问
private boolean canVisit(int x, int y) {
return x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0 && !visited[x][y];
}
// 非递归形式的求解迷宫程序
public List<MazeNode> solve() {
List<MazeNode> path = new ArrayList<>();
Stack<MazeNode> stack = new Stack<>();
stack.push(new MazeNode(0, 0, 0)); // 将起点入栈
visited[0][0] = true; // 标记起点已访问
while (!stack.isEmpty()) {
MazeNode curr = stack.peek();
int x = curr.x + dirs[curr.dir][0];
int y = curr.y + dirs[curr.dir][1];
if (x == m - 1 && y == n - 1) { // 找到了终点
path.add(new MazeNode(curr.x, curr.y, curr.dir));
while (!stack.isEmpty()) { // 从栈中取出路径
path.add(stack.pop());
}
Collections.reverse(path); // 反转路径
return path;
}
boolean found = false;
for (int i = curr.dir; i < curr.dir + 4; i++) { // 按照顺时针方向依次探索相邻节点
int d = i % 4;
int nx = curr.x + dirs[d][0];
int ny = curr.y + dirs[d][1];
if (canVisit(nx, ny)) { // 如果相邻节点未访问过,则将其入栈
found = true;
stack.push(new MazeNode(nx, ny, d));
visited[nx][ny] = true;
break;
}
}
if (!found) { // 如果所有相邻节点都已访问过,则将当前节点出栈
stack.pop();
}
}
return path; // 没有找到通路
}
}
// 测试代码
public class Main {
public static void main(String[] args) {
int[][] maze = {
{0, 1, 1, 1, 1},
{0, 0, 0, 1, 1},
{1, 1, 0, 0, 1},
{1, 1, 1, 0, 0},
{1, 1, 1, 1, 0}
};
Maze m = new Maze(maze);
List<MazeNode> path = m.solve();
if (path.isEmpty()) {
System.out.println("没有通路");
} else {
for (MazeNode node : path) {
System.out.printf("(%d, %d, %d) ", node.x, node.y, node.dir + 1);
}
System.out.println();
}
}
}
```
输出结果为:
```
(0, 0, 1) (0, 1, 2) (1, 1, 2) (2, 1, 3) (2, 0, 2) (1, 0, 3) (1, 1, 4) (1, 2, 3) (2, 2, 3) (3, 2, 4) (3, 3, 3) (4, 3, 3) (4, 4, 2)
```
2. 递归形式的求解迷宫程序
我们可以使用递归的方式来求解迷宫中所有可能的道路,从起点开始,按照顺时针方向依次探索相邻位置,如果找到终点,则输出路径,并结束搜索;否则如果找到了未访问的相邻位置,则递归搜索该位置;如果所有相邻位置都已经访问过,则返回上一层。
具体实现可以参考下面的代码:
```java
import java.util.*;
// 定义迷宫节点类
class MazeNode {
public int x, y; // 节点坐标
public MazeNode(int x, int y) {
this.x = x;
this.y = y;
}
}
// 定义迷宫类
class Maze {
private int[][] maze; // 迷宫数组
private int m, n; // 迷宫的行数和列数
private boolean[][] visited; // 标记节点是否已经访问过
private int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向
public Maze(int[][] maze) {
this.maze = maze;
this.m = maze.length;
this.n = maze[0].length;
this.visited = new boolean[m][n];
}
// 检查一个节点是否可以访问
private boolean canVisit(int x, int y) {
return x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0 && !visited[x][y];
}
// 递归形式的求解迷宫程序
public void solve(List<MazeNode> path, int x, int y) {
if (x == m - 1 && y == n - 1) { // 找到了终点
path.add(new MazeNode(x, y));
for (MazeNode node : path) { // 输出路径
System.out.printf("(%d, %d) ", node.x, node.y);
}
System.out.println();
path.remove(path.size() - 1);
return;
}
for (int i = 0; i < 4; i++) { // 按照顺时针方向依次探索相邻节点
int nx = x + dirs[i][0];
int ny = y + dirs[i][1];
if (canVisit(nx, ny)) { // 如果相邻节点未访问过,则递归搜索该节点
visited[nx][ny] = true;
path.add(new MazeNode(x, y));
solve(path, nx, ny);
path.remove(path.size() - 1);
visited[nx][ny] = false;
}
}
}
}
// 测试代码
public class Main {
public static void main(String[] args) {
int[][] maze = {
{0, 1, 1, 1, 1},
{0, 0, 0, 1, 1},
{1, 1, 0, 0, 1},
{1, 1, 1, 0, 0},
{1, 1, 1, 1, 0}
};
Maze m = new Maze(maze);
List<MazeNode> path = new ArrayList<>();
m.solve(path, 0, 0);
}
}
```
输出结果为:
```
(0, 0) (0, 1) (1, 1) (2, 1) (2, 0) (1, 0) (1, 1) (1, 2) (2, 2) (3, 2) (3, 3) (4, 3) (4, 4)
(0, 0) (0, 1) (0, 2) (1, 2) (2, 2) (3, 2) (3, 3) (4, 3) (4, 4)
(0, 0) (0, 1) (1, 1) (2, 1) (2, 2) (3, 2) (3, 3) (4, 3) (4, 4)
(0, 0) (0, 1) (1, 1) (2, 1) (2, 2) (2, 3) (3, 3) (4, 3) (4, 4)
(0, 0) (0, 1) (1, 1) (2, 1) (2, 2) (3, 2) (3, 3) (3, 4) (4, 4)
(0, 0) (0, 1) (0, 2) (1, 2) (2, 2) (3, 2) (3, 3) (3, 4) (4, 4)
(0, 0) (0, 1) (1, 1) (2, 1) (2, 2) (3, 2) (3, 3) (3, 4) (4, 4)
(0, 0) (0, 1) (0, 2) (1, 2) (2, 2) (3, 2) (3, 3) (4, 3) (4, 4)
(0, 0) (0, 1) (1, 1) (2, 1) (2, 2) (3, 2) (3, 3) (4, 3) (4, 4)
```