用Java实现,迷宫放在一个TXT文件中,求找到藏在迷宫中的15个宝藏并从出口住区最短路径,并输出路径,给出java代码
时间: 2024-02-13 13:02:14 浏览: 130
好的,以下是一份Java代码,用于实现你描述的问题:
```java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class MazeSolver {
private int[][] maze; // 迷宫图
private boolean[][] visited; // 是否访问过
private int[][] pred; // 前驱节点
private int rowSize; // 迷宫行数
private int colSize; // 迷宫列数
private ArrayList<Point> treasures; // 宝藏位置列表
private Point entrance; // 入口位置
private Point exit; // 出口位置
public MazeSolver(File file) throws FileNotFoundException {
parseMazeFile(file);
treasures = new ArrayList<>();
}
public void solve() {
bfs();
printPath();
}
private void parseMazeFile(File file) throws FileNotFoundException {
Scanner scanner = new Scanner(file);
rowSize = scanner.nextInt();
colSize = scanner.nextInt();
maze = new int[rowSize][colSize];
visited = new boolean[rowSize][colSize];
pred = new int[rowSize][colSize];
for (int i = 0; i < rowSize; i++) {
for (int j = 0; j < colSize; j++) {
maze[i][j] = scanner.nextInt();
visited[i][j] = false;
pred[i][j] = -1;
if (maze[i][j] == 2) { // 宝藏
treasures.add(new Point(i, j));
} else if (maze[i][j] == 3) { // 入口
entrance = new Point(i, j);
} else if (maze[i][j] == 4) { // 出口
exit = new Point(i, j);
}
}
}
}
private void bfs() {
Queue<Point> queue = new LinkedList<>();
queue.offer(entrance);
visited[entrance.x][entrance.y] = true;
while (!queue.isEmpty()) {
Point curr = queue.poll();
if (curr.equals(exit)) {
break;
}
int x = curr.x;
int y = curr.y;
// 搜索上下左右四个方向
if (x > 0 && !visited[x - 1][y] && maze[x - 1][y] != -1) {
queue.offer(new Point(x - 1, y));
visited[x - 1][y] = true;
pred[x - 1][y] = x * colSize + y;
}
if (x < rowSize - 1 && !visited[x + 1][y] && maze[x + 1][y] != -1) {
queue.offer(new Point(x + 1, y));
visited[x + 1][y] = true;
pred[x + 1][y] = x * colSize + y;
}
if (y > 0 && !visited[x][y - 1] && maze[x][y - 1] != -1) {
queue.offer(new Point(x, y - 1));
visited[x][y - 1] = true;
pred[x][y - 1] = x * colSize + y;
}
if (y < colSize - 1 && !visited[x][y + 1] && maze[x][y + 1] != -1) {
queue.offer(new Point(x, y + 1));
visited[x][y + 1] = true;
pred[x][y + 1] = x * colSize + y;
}
}
}
private void printPath() {
if (!visited[exit.x][exit.y]) {
System.out.println("无解");
return;
}
ArrayList<Point> path = new ArrayList<>();
int curr = exit.x * colSize + exit.y;
while (curr != entrance.x * colSize + entrance.y) {
int x = curr / colSize;
int y = curr % colSize;
path.add(new Point(x, y));
curr = pred[x][y];
}
path.add(entrance);
System.out.println("最短路径为:");
for (int i = path.size() - 1; i >= 0; i--) {
Point point = path.get(i);
System.out.printf("(%d, %d)\n", point.x, point.y);
}
System.out.println("宝藏搜寻顺序为:");
for (int i = 0; i < treasures.size(); i++) {
Point treasure = treasures.get(i);
if (visited[treasure.x][treasure.y]) {
System.out.printf("(%d, %d)\n", treasure.x, treasure.y);
}
}
}
public static void main(String[] args) throws FileNotFoundException {
File file = new File("maze.txt");
MazeSolver solver = new MazeSolver(file);
solver.solve();
}
private static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public boolean equals(Point other) {
return x == other.x && y == other.y;
}
}
}
```
这份代码使用了宽度优先搜索算法来寻找从入口到出口的最短路径,并用一个数组来记录路径中每个节点的前驱节点。在找到最短路径后,程序会沿着前驱节点的方向逆推路径,最终得到从入口到出口的最短路径,并输出宝藏的搜寻顺序。注意,这份代码并没有实现宝藏的搜寻过程,需要根据需要自行实现。
阅读全文