Java 中基于深度优先搜索的迷宫生成与求解210

迷宫是一种益智游戏，玩家必须沿着一条路径从起点走到终点，同时避免死胡同。迷宫可以通过各种算法来生成和求解，而深度优先搜索（DFS）是一种特别适合此任务的算法。

迷宫生成

使用 DFS 生成迷宫涉及创建网格并随机选择一个网格单元格作为起点。然后算法递归地从该单元格向四个方向（上、下、左、右）探索相邻单元格。如果相邻单元格未被访问过，则将它添加到迷宫中并将其作为新的起点继续探索。该过程一直持续到所有单元格都被访问过。
import ;
public class MazeGenerator {
private int[][] maze;
private int width;
private int height;
public MazeGenerator(int width, int height) {
= width;
= height;
maze = new int[height][width];
}
public void generateMaze() {
Random random = new Random();
int currentRow = (height);
int currentCol = (width);
maze[currentRow][currentCol] = 1; // 标记起点
while (hasUnvisitedCells()) {
int[] neighbors = getUnvisitedNeighbors(currentRow, currentCol);
if ( > 0) {
int index = ();
int nextRow = neighbors[index] / width;
int nextCol = neighbors[index] % width;
maze[nextRow][nextCol] = 1; // 标记下一个单元格
// 挖通墙壁
if (currentRow == nextRow) {
maze[currentRow][(currentCol + nextCol) / 2] = 1;
} else {
maze[(currentRow + nextRow) / 2][currentCol] = 1;
}
// 更新当前单元格
currentRow = nextRow;
currentCol = nextCol;
} else {
// 回溯
backtrack(currentRow, currentCol);
}
}
}
private boolean hasUnvisitedCells() {
for (int row = 0; row < height; row++) {
for (int col = 0; col < width; col++) {
if (maze[row][col] == 0) {
return true;
}
}
}
return false;
}
private int[] getUnvisitedNeighbors(int row, int col) {
int[] neighbors = new int[4];
int count = 0;
// 上
if (row > 0 && maze[row - 1][col] == 0) {
neighbors[count++] = (row - 1) * width + col;
}
// 下
if (row < height - 1 && maze[row + 1][col] == 0) {
neighbors[count++] = (row + 1) * width + col;
}
// 左
if (col > 0 && maze[row][col - 1] == 0) {
neighbors[count++] = row * width + (col - 1);
}
// 右
if (col < width - 1 && maze[row][col + 1] == 0) {
neighbors[count++] = row * width + (col + 1);
}
return neighbors;
}
private void backtrack(int row, int col) {
// 标记为已访问
maze[row][col] = 2;
// 回溯到上一个未访问的单元格
for (int r = row - 1; r >= 0; r--) {
if (maze[r][col] == 0) {
currentRow = r;
currentCol = col;
return;
}
}
for (int c = col - 1; c >= 0; c--) {
if (maze[row][c] == 0) {
currentRow = row;
currentCol = c;
return;
}
}
}
public int[][] getMaze() {
return maze;
}
}

迷宫求解

使用 DFS 求解迷宫涉及从起点开始对相邻单元格进行递归探索。如果相邻单元格是终点，则算法返回一个解决方案。否则，算法标记该单元格为已访问并继续探索相邻单元格。该过程一直持续到找到解决方案或所有相邻单元格都被访问过。
import ;
public class MazeSolver {
private int[][] maze;
private int width;
private int height;
public MazeSolver(int[][] maze) {
= maze;
= maze[0].length;
= ;
}
public boolean solveMaze() {
Stack path = new Stack();
(new int[]{0, 0}); // 将起点添加到路径中
while (!()) {
int[] current = (); // 获取当前单元格
if (current[0] == height - 1 && current[1] == width - 1) { // 到达终点
return true;
}
// 标记为已访问
maze[current[0]][current[1]] = 2;
// 探索相邻单元格
int[] neighbors = getUnvisitedNeighbors(current[0], current[1]);
for (int[] neighbor : neighbors) {
(neighbor);
}
}
return false;
}
private int[] getUnvisitedNeighbors(int row, int col) {
int[] neighbors = new int[4];
int count = 0;
// 上
if (row > 0 && maze[row - 1][col] == 0) {
neighbors[count++] = new int[]{row - 1, col};
}
// 下
if (row < height - 1 && maze[row + 1][col] == 0) {
neighbors[count++] = new int[]{row + 1, col};
}
// 左
if (col > 0 && maze[row][col - 1] == 0) {
neighbors[count++] = new int[]{row, col - 1};
}
// 右
if (col < width - 1 && maze[row][col + 1] == 0) {
neighbors[count++] = new int[]{row, col + 1};
}
return neighbors;
}
}

示例

以下示例演示了如何使用 DFS 生成和求解迷宫：
public class Main {
public static void main(String[] args) {
MazeGenerator generator = new MazeGenerator(10, 10);
();
int[][] maze = ();
MazeSolver solver = new MazeSolver(maze);
boolean solved = ();
if (solved) {
("迷宫已求解");
} else {
("迷宫无解");
}
}
}

深度优先搜索（DFS）是一种生成和求解迷宫的有效算法。通过递归探索网格中的单元格，DFS 可以找到一条从起点到终点的路径，或者确定迷宫无解。使用 Java 实现 DFS 既简单又高效，使该算法成为解决迷宫问题的理想选择。

2024-10-27

上一篇：用 Java 为字符赋值

下一篇：Java 数据封装：保护和管理你的数据