迷宫问题
迷宫问题
使用队列和BFS算法来解决迷宫问题:
我们定义了一个MazeSolver类,它包含一个二维数组maze表示迷宫地图,以及迷宫的行数rows和列数cols。我们使用BFS算法来搜索从起点(startX, startY)到终点(endX, endY)的路径,具体实现如下:
-
首先创建一个visited数组,用于标记每个位置是否已经访问过,初始时全部为false。
-
创建一个队列queue,将起点(startX, startY)加入队列中,并将其标记为已访问。
-
循环执行以下步骤,直到队列为空:
-
弹出队列中的第一个位置(x, y)。
-
如果(x, y)是终点(endX, endY),则搜索完成,返回true。
-
遍历四个方向,对于每个方向,计算出下一个位置(nx, ny),如果下一个位置越界、是障碍物或已经访问过,则不能继续访问,否则将该位置加入队列中,并标记为已访问。
-
如果队列为空仍然没有找到终点,则搜索失败,返回false。
-
在上面的main方法中,我们创建了一个迷宫地图,并使用MazeSolver类来搜索从起点(0, 0)到终点(3, 3)的路径。如果找到了路径,则输出"可以到达终点",否则输出"无法到达终点"。
代码实现
package demo.data;import java.util.LinkedList;
import java.util.Queue;public class MazeSolver {private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向private int[][] maze; // 迷宫地图private int rows, cols; // 迷宫的行数和列数public MazeSolver(int[][] maze) {this.maze = maze;this.rows = maze.length;this.cols = maze[0].length;}public boolean solve(int startX, int startY, int endX, int endY) {boolean[][] visited = new boolean[rows][cols]; // 标记每个位置是否已经访问过Queue<int[]> queue = new LinkedList<>(); // 存储待访问的位置queue.offer(new int[] {startX, startY});visited[startX][startY] = true;while (!queue.isEmpty()) {int[] curr = queue.poll();int x = curr[0], y = curr[1];if (x == endX && y == endY) { // 找到了终点return true;}for (int[] dir : DIRS) { // 遍历四个方向int nx = x + dir[0], ny = y + dir[1];if (nx < 0 || nx >= rows || ny < 0 || ny >= cols || maze[nx][ny] == 1 || visited[nx][ny]) {// 越界、障碍物或已经访问过,都不能继续访问continue;}queue.offer(new int[] {nx, ny});visited[nx][ny] = true;}}return false; // 没有找到终点}public static void main(String[] args) {int[][] maze = {{0, 1, 0, 0},{0, 0, 0, 1},{1, 0, 1, 0},{0, 0, 0, 0}};MazeSolver solver = new MazeSolver(maze);boolean found = solver.solve(0, 0, 3, 3);System.out.println(found ? "可以到达终点" : "无法到达终点");}
}
定义了一个5×5的迷宫,用二维数组 maze 表示,并输出迷宫。
- 接着,定义起点和终点的坐标为 (0, 0) 和 (4, 4),并定义队列 queue 和标记数组 visited,将起点加入队列,并标记起点已访问。
- 定义方向数组 directions,依次为上、右、下、左,用于依次尝试四个方向。
- 定义变量 endNode 用于存储最短路线,初始值为 null。
- 接着,进行广度优先搜索,取出队列第一个元素,判断是否为终点,若是,则记录该节点并退出循环;否则,依次尝试四个方向,判断下一个位置是否越界或为墙壁,若是,则跳过;判断下一个位置是否已经访问过,若是,则跳过;否则,将下一个位置加入队列,并标
代码实现
package demo.data;import java.util.LinkedList;public class migong {public static void main(String[] args) {// 定义迷宫int[][] maze = {{0, 1, 0, 0, 0},{0, 1, 0, 1, 0},{0, 0, 0, 0, 0},{0, 1, 1, 1, 0},{0, 0, 0, 1, 0}};// 输出迷宫System.out.println("迷宫:");for (int i = 0; i < maze.length; i++) {for (int j = 0; j < maze[i].length; j++) {System.out.print(maze[i][j] + " ");}System.out.println();}// 定义起点和终点int startX = 0, startY = 0;int endX = 4, endY = 4;// 定义队列和标记数组LinkedList<Node> queue = new LinkedList<>();boolean[][] visited = new boolean[5][5];// 将起点加入队列queue.offer(new Node(startX, startY, 0, null));// 标记起点已访问visited[startX][startY] = true;// 定义方向数组,依次为上、右、下、左int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};// 定义变量用于存储最短路线Node endNode = null;// 广度优先搜索while (!queue.isEmpty()) {// 取出队列第一个元素Node curr = queue.poll();// 如果当前位置是终点,记录该节点并退出循环if (curr.x == endX && curr.y == endY) {endNode = curr;break;}// 否则,依次尝试上、右、下、左四个方向for (int[] direction : directions) {int nextX = curr.x + direction[0];int nextY = curr.y + direction[1];// 判断下一个位置是否越界或为墙壁,若是,则跳过if (nextX < 0 || nextX >= 5 || nextY < 0 || nextY >= 5 || maze[nextX][nextY] == 1) {continue;}// 判断下一个位置是否已经访问过,若是,则跳过if (visited[nextX][nextY]) {continue;}// 将下一个位置加入队列,并标记已访问queue.offer(new Node(nextX, nextY, curr.step + 1, curr));visited[nextX][nextY] = true;}}// 输出最短路线System.out.println("最短路线:");printPath(endNode);}// 输出一条路径public static void printPath(Node endNode) {if (endNode == null) {return;}printPath(endNode.parent);System.out.println("(" + endNode.x + ", " + endNode.y + ")");}// 定义节点类private static class Node {int x, y; //节点坐标int step; //到达该节点的步数Node parent; //到达该节点的上一节点public Node(int x, int y, int step, Node parent) {this.x = x;this.y = y;this.step = step;this.parent = parent;}}}