Java 中二元迷宫的最短路径

2024年9月10日 | 阅读13分钟

输入是一个 MxN 矩阵，元素可能为 0 或 1。需要找到给定源单元格和目标单元格之间的最短路径。只有值为 1 的单元格才能用于构成路径。

示例

输入: mat[ROW][COL] = {{1,0,1,1,1},

{1,0,1,0,1},

{1,1,1,0,1},

{0,0,0,0,1},

{1,1,1,0,1}};

源单元格为 (0,0)，目标单元格为 (4,4)。

输出: 最短路径: 12

方法: 使用深度优先搜索 (DFS)

假设迷宫中，值为 1 的是墙，值为 0 的是可通行空间。算法从迷宫的左上角开始，通过递归探索迷宫的所有可能路径，直到到达右下角。它会跟踪迄今为止找到的路径长度，并在到达目标时更新最小路径长度。如果找不到路径，则返回 -1。

文件名: ShortestPathDFS.java

// A Java program to find the shortest path in a maze using DFS algorithm
import java.util.*;
public class ShortestPathDFS {
// Declare a private variable to store the shortest path
private static int shortestPath;

// Method to find the shortest path in a given maze
public static int findShortestPath(int[][] maze) {
    
    // Check if the maze is empty or null, if so return 0
    if (maze == null || maze.length == 0 || maze[0].length == 0) {
        return 0;
    }
    
    // Initialize shortestPath to the maximum possible value
    shortestPath = Integer.MAX_VALUE;
    
    // Initialize a boolean array to keep track of visited cells
    boolean[][] visited = new boolean[maze.length][maze[0].length];
    
    // Invoke the dfs() method to find the shortest path
    dfs(maze, visited, 0, 0, 0);
    
    // Return the shortest path, or 0 if it was not found
    return shortestPath == Integer.MAX_VALUE ? 0 : shortestPath;
}

// Method to perform DFS traversal to find the shortest path
private static void dfs(int[][] maze, boolean[][] visited, int row, int col, int distance) {
    
    // Check if the current cell is out of bounds, a wall or has already been visited
    if (row < 0 || row >= maze.length || col < 0 || col >= maze[0].length || maze[row][col] == 0 || visited[row][col]) {
        return;
    }
    
    // Check if the current cell is the destination, if so update the shortestPath variable and return
    if (row == maze.length - 1 && col == maze[0].length - 1) {
        shortestPath = Math.min(shortestPath, distance);
        return;
    }
    
    // Mark the current cell as visited
    visited[row][col] = true;
    
    // Explore all possible paths from the current cell
    dfs(maze, visited, row + 1, col, distance + 1);
    dfs(maze, visited, row - 1, col, distance + 1);
    dfs(maze, visited, row, col + 1, distance + 1);
    dfs(maze, visited, row, col - 1, distance + 1);
    
    // Unmark the current cell as visited
    visited[row][col] = false;
}

// Main method to test the code
public static void main(String[] args) {
    
    // Initialize a 2D array to represent the maze
    int[][] maze = {
        {1, 0, 1, 1, 1},
        {1, 0, 1, 0, 1},
        {1, 1, 1, 0, 1},
        {0, 0, 0, 0, 1},
        {1, 1, 1, 0, 1}
    };
    
    // Find the shortest path in the maze using DFS and print it
    int shortest = findShortestPath(maze);
    System.out.println("Shortest Path using DFS: " + shortest);
}
}

输出

Shortest Path using DFS: 12

说明: 给定的 Java 程序实现了深度优先搜索 (DFS) 算法，用于查找由二维整数数组表示的迷宫中的最短路径。程序以迷宫为输入，并初始化一个布尔数组来跟踪访问过的单元格。它从左上角的单元格 (0,0) 开始探索迷宫，并递归遍历所有可能的路径，直到到达右下角的单元格 (maze.length-1, maze[0].length-1) 或死胡同。在遍历过程中，程序为每个访问过的单元格将距离加 1，并在找到到目标单元格的更短路径时更新 shortestPath 变量。最后，它返回 shortestPath 值，如果不存在路径则返回 0。该程序还包含一个 main 方法，通过传递给定的输入迷宫并使用 DFS 打印最短路径来演示 findShortestPath 方法的功能。

复杂度分析: 此实现的 time complexity 为 O(m * n)，其中 m 是输入迷宫的行数，n 是列数。原因是，在 DFS 算法中，迷宫中的每个单元格最多被访问一次。

space complexity 也为 O(m * n)，这是因为创建了一个布尔 visited 数组来跟踪访问过的单元格。此外，DFS 算法的递归性质在最坏情况下可能导致较大的堆栈空间使用。然而，由于此实现中的迷宫相对较小，因此这不是一个重大问题。

总的来说，此实现简单易懂，但对于较大的迷宫可能不是最高效的。其他算法，例如 Dijkstra 算法或 A* 搜索，对于更大、更复杂的迷宫可能提供更好的性能。

方法: 使用 Dijkstra 算法

文件名: BinaryMazeShortestPath.java

import java.util.*;
public class DijkstraShortestPath {
// constant representing infinity
static final int INF = Integer.MAX_VALUE;

public static int shortestPath(int[][] maze, int startX, int startY, int endX, int endY) {
    int n = maze.length;
    int m = maze[0].length;

    // arrays representing the directions for moving in the maze
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};

    // 2D arrays representing the shortest distances and visited cells
    int[][] dist = new int[n][m];
    boolean[][] visited = new boolean[n][m];

    // initialize all distances to infinity except the starting cell
    for (int i = 0; i < n; i++) {
        Arrays.fill(dist[i], INF);
    }
    dist[startX][startY] = 0;

    // create a priority queue for storing cells to visit
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
    pq.offer(new int[]{startX, startY, 0});

    // iterate while there are cells to visit
    while (!pq.isEmpty()) {
        // remove the cell with the smallest distance from the priority queue
        int[] curr = pq.poll();
        int x = curr[0];
        int y = curr[1];
        int d = curr[2];

        // if the cell has already been visited, skip it
        if (visited[x][y]) {
            continue;
        }

        // mark the cell as visited
        visited[x][y] = true;

        // if we've reached the end cell, return the shortest distance
        if (x == endX && y == endY) {
            return d;
        }

        // iterate over the neighboring cells and update their distances if necessary
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == 1 && !visited[nx][ny]) {
                int nd = d + 1;
                if (nd < dist[nx][ny]) {
                    dist[nx][ny] = nd;
                    pq.offer(new int[]{nx, ny, nd});
                }
            }
        }
    }

    // if we couldn't reach the end cell, return -1
    return -1;
}

public static void main(String[] args) {
    int[][] maze = {
            {1, 0, 1, 1, 1},
            {1, 0, 1, 0, 1},
            {1, 1, 1, 0, 1},
            {0, 0, 0, 0, 1},
            {1, 1, 1, 0, 1}
    };
    int startX = 0;
    int startY = 0;
    int endX = 4;
    int endY = 4;

    // calculate the shortest path in the maze
    int shortestPath = shortestPath(maze, startX, startY, endX, endY);

    // print the result
    System.out.println("Shortest path length: " + shortestPath);
}
}

输出

Shortest path length: 12

说明: 上面的代码实现了 Dijkstra 算法，用于查找迷宫中两点之间的最短路径。迷宫表示为二维数组，其中 1 表示路径，0 表示墙。该算法使用优先队列来选择距离源单元格最近的未访问单元格。

shortestPath 函数接收迷宫、起始坐标 (startX 和 startY) 和结束坐标 (endX 和 endY) 作为输入，并返回起点和终点之间的最短路径长度。

该函数初始化 dist 数组，除了起点单元格（设为 0）外，所有单元格都设置为无穷大。它还初始化一个 visited 数组来跟踪访问过的单元格。

算法首先将起点单元格添加到优先队列中，距离为 0。它将继续循环，直到优先队列为空或到达终点单元格。在每次迭代中，从队列中选择距离最小的单元格，并探索其邻居。如果找到更短的路径，则更新每个邻居的距离，并将其添加到优先队列中。

如果无法到达终点单元格，则方法返回 -1；如果到达终点单元格，则返回最短路径长度。

main 方法创建一个迷宫，并使用起始和结束坐标调用 shortestPath 函数。最短路径的长度将打印到控制台。

复杂度分析: 给定代码中 Dijkstra 算法实现的 time complexity 为 O(N^2 log N)，其中 N 是输入网格中的节点数（或单元格数）。原因是，我们使用优先队列来处理网格中每个节点的邻接节点，每次插入或删除最多需要 O(log N) 时间，并且我们确保每个节点只处理一次。在最坏情况下，可能会访问所有节点，因此 overall time complexity 为 O(N^2 log N)。space complexity 也为 O(N^2)，因为算法在两个独立的 N x N 数组中存储每个节点的距离和访问状态。

方法: 使用广度优先搜索算法

广度优先搜索 (BFS) 是用于查找二进制迷宫中最短路径的最常用算法之一。它通过在移动到其邻居之前探索一个单元格的所有邻居来工作。

文件名: ShortestPathBinaryMaze.java

import java.util.*;

public class ShortestPathBinaryMaze {
// A class to store the coordinates of a matrix cell
static class Point {
    int row, col;

    public Point(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

// Check if a cell (row, col) is a valid cell or not
static boolean isValid(int[][] maze, int row, int col) {
    int rows = maze.length, cols = maze[0].length;
    return (row >= 0 && row < rows && col >= 0 && col < cols && maze[row][col] == 1);
}

// Find the shortest path in binary maze from source to destination using BFS
static int shortestPathBFS(int[][] maze, Point src, Point dest) {
    int rows = maze.length, cols = maze[0].length;

    // Array to store the distance of each cell from the source
    int[][] dist = new int[rows][cols];
    for (int[] row : dist) {
        Arrays.fill(row, Integer.MAX_VALUE);
    }

    // The source cell has distance of 0 from itself
    dist[src.row][src.col] = 0;

    // Create a queue for BFS
    Queue<Point> q = new LinkedList<>();
    q.add(src); // Enqueue the source cell

    // Arrays to get row and column numbers of 4 neighbors of a cell
    int[] rowNum = {-1, 0, 1, 0};
    int[] colNum = {0, -1, 0, 1};

    // Perform BFS
    while (!q.isEmpty()) {
        Point curr = q.poll();

        // If we have reached the destination cell, we are done
        if (curr.row == dest.row && curr.col == dest.col) {
            return dist[curr.row][curr.col];
        }

        // Visit all neighbors of the current cell
        for (int i = 0; i < 4; i++) {
            int row = curr.row + rowNum[i];
            int col = curr.col + colNum[i];

            // If the adjacent cell is valid, has a path, and not visited yet, enqueue it
            if (isValid(maze, row, col) && dist[row][col] > dist[curr.row][curr.col] + 1) {
                // Update the distance of the neighbor cell from the source
                dist[row][col] = dist[curr.row][curr.col] + 1;
                q.add(new Point(row, col)); // Enqueue the neighbor cell
            }
        }
    }

    // Destination cannot be reached
    return -1;
}

// Driver code
public static void main(String[] args) {
    int[][] maze = {
        {1, 0, 1, 1, 1},
        {1, 0, 1, 0, 1},
        {1, 1, 1, 0, 1},
        {0, 0, 0, 0, 1},
        {1, 1, 1, 0, 1}};

// create a starting point for the path
Point src = new Point(0, 0);

// create an ending point for the path
Point dest = new Point(4, 4);

// find the shortest path in the binary maze from the starting point to the ending point using BFS
int shortestPath = shortestPathBFS(maze, src, dest);

// if the shortest path is not possible, print a message
if (shortestPath == -1) {
System.out.println("Destination cannot be reached");
}
// otherwise, print the length of the shortest path
else {
System.out.println("Shortest path length: " + shortestPath);
}
}
}

输出

Shortest path length: 12

说明: 上面的 Java 代码实现了广度优先搜索 (BFS) 算法，用于查找从源点到目标点在二进制迷宫中的最短路径。代码定义了一个嵌套类 Point 来存储矩阵单元格的坐标，并使用二维整型数组表示迷宫，其中 1 表示有效单元格，0 表示阻塞单元格。isValid 函数检查一个单元格是否在迷宫边界内并且是可通行的有效单元格。shortestPathBFS 函数使用队列对迷宫执行 BFS，从源点开始，直到到达目标点停止。每个单元格到源点的距离存储在二维整型数组 dist 中，该函数返回目标点到源点的距离，如果无法到达目标点则返回 -1。

复杂度分析

时间复杂度分析: BFS 算法的时间复杂度为 O(V+E)，其中 V 是顶点数，E 是边数。在这种情况下，顶点数等于矩阵中的单元格数，即 rows x cols。在最坏情况下，边数可以视为 O(V)，因为每个单元格最多可以有 4 条边（上、下、左、右），并且在最坏情况下，所有单元格都相互连接。因此，算法的时间复杂度为 O(rows x cols)，因为 V = rows x cols 且 E = O(V)。

空间复杂度分析: 算法的空间复杂度为 O(V)，其中 V 是顶点数，即 rows x cols。原因是，我们通过维护一个 rows x cols 维度的距离矩阵来跟踪每个单元格到源点的距离。此外，我们使用一个队列来存储要访问的单元格，该队列在最坏情况下最多可以包含 V 个元素。

总的来说，算法的时间复杂度为 O(rows x cols)，空间复杂度为 O(rows x cols)。

方法: 使用回溯

回溯算法通过递归地探索搜索空间，将每个候选解标记为成功或失败，然后撤销每个选择，直到找到有效解或耗尽所有可能性。

实施

文件名: ShortestPathBacktracking.java

public class ShortestPathBacktracking {

    public static int findShortestPath(int[][] maze) {
        // Get the number of rows and columns in the maze
        int rows = maze.length;
        int cols = maze[0].length;

        // Create a boolean matrix to track visited cells
        boolean[][] visited = new boolean[rows][cols];

        // Initialize the shortest path to a very large number
        int[] shortestPath = {Integer.MAX_VALUE};

        // Call the recursive helper function to find the shortest path
        findShortestPath(maze, visited, 0, 0, rows - 1, cols - 1, 0, shortestPath);

        // Return the shortest path found
        return shortestPath[0];
    }

    private static void findShortestPath(int[][] maze, boolean[][] visited, int row, int col, int endRow, int endCol, int distance, int[] shortestPath) {
        // Check if the current cell is out of bounds, is blocked, or has already been visited
        if (row < 0 || row >= maze.length || col < 0 || col >= maze[0].length || maze[row][col] == 0 || visited[row][col]) {
            return; // If so, backtrack
        }
        
        // Check if the current cell is the destination
        if (row == endRow && col == endCol) {
            shortestPath[0] = Math.min(shortestPath[0], distance); // Update the shortest path found so far
            return; // Backtrack
        }
        
        // Mark the current cell as visited
        visited[row][col] = true;

        // Recursively call the function to explore the neighboring cells in all four directions
        findShortestPath(maze, visited, row + 1, col, endRow, endCol, distance + 1, shortestPath); // move down
        findShortestPath(maze, visited, row - 1, col, endRow, endCol, distance + 1, shortestPath); // move up
        findShortestPath(maze, visited, row, col + 1, endRow, endCol, distance + 1, shortestPath); // move right
        findShortestPath(maze, visited, row, col - 1, endRow, endCol, distance + 1, shortestPath); // move left

        // Mark the current cell as unvisited (for backtracking)
        visited[row][col] = false;
    }

    public static void main(String[] args) {
        // Create a 2D array representing the maze
        int[][] maze = {{1, 0, 1, 1, 1},
                        {1, 0, 1, 0, 1},
                        {1, 1, 1, 0, 1},
                        {0, 0, 0, 0, 1},
                        {1, 1, 1, 0, 1}};

        // Call the findShortestPath function to get the shortest path from the top-left cell to the bottom-right cell
        int shortestPath = findShortestPath(maze);

        // Print the shortest path found
        System.out.println("Shortest Path: " + shortestPath);
    }
}

输出

Shortest Path: 12

说明: ShortestPathBacktracking 类包含一个名为 findShortestPath 的递归方法，该方法使用回溯从起始点 (0,0) 到结束点 (rows-1,cols-1) 在迷宫中查找最短路径。迷宫由二维整型数组表示，其中 1 表示有效路径，0 表示墙。该算法使用一个名为 visited 的布尔数组来跟踪访问过的单元格。

findShortestPath 方法接收迷宫、visited 数组、当前行和列、结束行和列、当前距离以及一个用于存储迄今为止找到的最短路径的数组作为输入。它首先检查当前单元格是否有效且未被访问。如果它是结束单元格，它将更新最短路径（如果当前距离小于迄今为止找到的最短路径）。然后它将当前单元格标记为已访问，并递归调用自身来处理四个可能的移动：下、上、右和左。每次递归调用后，它都会取消设置当前单元格的 visited 标志，以便它可以在不同的路径中再次被访问。

main 方法初始化迷宫并调用 findShortestPath 方法，然后打印结果。

复杂度分析: 该算法在最坏情况下的 time complexity 为 O(4^(nm))，其中 n 是迷宫的行数，m 是列数。通过为每个单元格探索四种可能的方向，我们使用递归深度优先搜索来导航迷宫，直到到达目标单元格。在最坏情况下，我们可能需要探索迷宫中的所有可能路径，这将使我们总共考虑 4^(nm) 条可能的路径。

该算法的 space complexity 为 O(nm)，其中 n 是迷宫的行数，m 是列数。使用布尔矩阵来跟踪访问过的单元格，其尺寸与迷宫相同。此外，我们使用一个递归函数，该函数最多可以调用自身 nm 次，这可能导致最大调用堆栈深度为 n*m。

下一个主题Java 中的自定义异常

Java 中二元迷宫的最短路径

方法: 使用深度优先搜索 (DFS)

方法: 使用 Dijkstra 算法

方法: 使用广度优先搜索算法

复杂度分析

方法: 使用回溯

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中二元迷宫的最短路径

方法: 使用深度优先搜索 (DFS)

方法: 使用 Dijkstra 算法

方法: 使用广度优先搜索算法

复杂度分析

方法: 使用回溯

实施

相关帖子

Wait vs Sleep in Java

Java 中的好数程序

DoubleBuffer mark() methods in Java with Examples

Java 中的 DoubleBuffer compact() 方法及示例

Java 中运算符的结合性

检查字符串中是否包含两个单词（Java）

Java Program to Detect Loop in Linked List

Heap Sort in Java

Java 程序获取目录大小

Java 中的 Rencontres 数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器