Java: 在二维矩阵中打印最短路径的有效方法

Question

下面是找出最短路径的代码，我试图只打印最短路径，但我得到了所有可能访问过的路径，我能够在 Python 中做到这一点，但是我在 Java 中很难做到这一点，我想知道在 Java 中是否有更好的方法来做到这一点。

Python解法

def helper(grid):
    m,n=len(grid),len(grid[0])
    deque=collections.deque([[(0,0)]])
    seen=set()
    while deque:
        arr=deque.popleft()
        i,j=arr[-1]
        if (i,j)==(m-1,n-1):
            return arr
        seen.add((i,j))
        possible=[(x,y) for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)] if 0<=x<m and 0<=y<n and grid[x][y]!=1]
        for x,y in possible:
            if (x,y) not in seen:
                deque.append(arr+[(x,y)])
        
grid=[
    [0,0,0,0,0,0,0],
    [0,0,1,0,0,1,0],
    [0,0,1,0,1,1,0],
    [0,0,1,0,1,0,1],
    [1,1,1,0,0,0,0]
]

print(helper(grid))

Python 代码将预期输出打印为 (0, 0) -> (0, 1) -> (0, 2) -> (0, 3) -> (1, 3) -> (2, 3) -> (3, 3) -> (4, 3) -> (4, 4) -> (4, 5) -> (4, 6)

Java

    import java.util.*;
    class Main {
 
    private static int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public static void main(String[] args) {
        int[][] grid = {
                {0, 0, 0, 0, 0, 0, 0},
                {0, 0, 1, 0, 0, 1, 0},
                {0, 0, 1, 0, 1, 1, 0},
                {0, 0, 1, 0, 1, 0, 1},
                {1, 1, 1, 0, 0, 0, 0}
        };
        int[][] path = shortestPath(grid);
        System.out.println("shortestPath " + Arrays.deepToString(path));
       
    }

    public static int[][] shortestPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        if (grid == null || grid.length == 0 || grid[0][0] == 1 || grid[m - 1][n - 1] == 1) return  new int[][]{{-1, -1}};
        int[][] path = bfs_with_visited(grid, m, n);
        return path;
    }

    private static int[][] bfs_with_visited(int[][] grid, int m, int n) {
        boolean[][] visited = new boolean[m][n];
        visited[0][0] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        List<int[]> result = new ArrayList<>();
        int path = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] currentCell = queue.remove();
                result.add(new int[]{currentCell[0], currentCell[1]});
                if (currentCell[0] == m - 1 && currentCell[1] == n - 1) {
                    return result.toArray(new int[result.size()][2]);
                }
                visitNeighbours(grid, m, n, visited, queue, currentCell);
            }
            path++;
        }
        return new int[][]{{-1, -1}};
    }

    private static void visitNeighbours(int[][] grid, int m, int n, boolean[][] visited, Queue<int[]> queue, int[] currentCell) {
        for (int k = 0; k < dir.length; k++) {
            int nextX = dir[k][0] + currentCell[0];
            int nextY = dir[k][1] + currentCell[1];

            if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && !visited[nextX][nextY] && grid[nextX][nextY] == 0) {

                queue.add(new int[]{nextX, nextY});
                visited[nextX][nextY] = true;
            }
        }
    }
}

感谢您的意见，TIA。

Answer 1

在您的 python 程序中，如果您在 arr = deque.popleft() 之后放置打印语句，您将看到以下内容：

[(0, 0)]
[(0, 0), (1, 0)]
[(0, 0), (0, 1)]
[(0, 0), (1, 0), (2, 0)]
[(0, 0), (1, 0), (1, 1)]
[(0, 0), (0, 1), (1, 1)]
[(0, 0), (0, 1), (0, 2)]
[(0, 0), (1, 0), (2, 0), (3, 0)]
[(0, 0), (1, 0), (2, 0), (2, 1)]
[(0, 0), (1, 0), (1, 1), (2, 1)]
[(0, 0), (0, 1), (1, 1), (2, 1)]
[(0, 0), (0, 1), (0, 2), (0, 3)]
[(0, 0), (1, 0), (2, 0), (3, 0), (3, 1)]
[(0, 0), (1, 0), (2, 0), (2, 1), (3, 1)]
[(0, 0), (1, 0), (1, 1), (2, 1), (3, 1)]
[(0, 0), (0, 1), (1, 1), (2, 1), (3, 1)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3)]
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (1, 4)]
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 4)]
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)]
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3)]
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (1, 6)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3), (4, 4)]
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (1, 6), (2, 6)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3), (4, 4), (4, 5)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3), (4, 4), (4, 5), (3, 5)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3), (4, 4), (4, 5), (4, 6)]

如果你看到，python 程序正在将一个列表附加到队列中，而不仅仅是一个坐标，这意味着它会记住它经过的路径，或者换句话说，它会一直携带路径。

如果你想在Java中模拟同样的事情，你可以按如下方式进行：

 private static int[][] bfs_with_visited(int[][] grid, int m, int n) {
        boolean[][] visited = new boolean[m][n];
        visited[0][0] = true;
        Deque<List<int[]>> queue = new ArrayDeque<>();
        List<int[]> result = new ArrayList<>();
        result.add(new int[] {0,0});
        queue.addFirst(result);
        while (!queue.isEmpty()) {
            
            int size = queue.size();
            for (int i = 0; i <size; i++ ) {
                result = queue.removeFirst();
                int[] curr = result.get(result.size()-1);
                
                if (curr[0] == m-1 && curr[1] == n-1) {
                    return result.toArray(new int[result.size()][2]);
                }
                
                visited[curr[0]][curr[1]] = true;
                visitNeighbours(grid, m, n, visited, queue, result, curr);
            }
            
            
        }
        return new int[][]{{-1, -1}};
    }

    private static void visitNeighbours(int[][] grid, int m, int n, boolean[][] visited, Deque<List<int[]>> queue, 
            List<int[]> listSoFar, int[] currentCell) {
        for (int k = 0; k < dir.length; k++) {
            int nextX = dir[k][0] + currentCell[0];
            int nextY = dir[k][1] + currentCell[1];

            if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && !visited[nextX][nextY] && grid[nextX][nextY] == 0) {
                List<int[]> l = new ArrayList<>(listSoFar);
                l.add(new int[] {nextX, nextY});
                queue.add(l);

            }
        }
    }

但我不会建议这样做。而是创建一个 class like

class Node {
   int[] prev = null;
   int[] curr = null;
   public Node(int[] curr, int[] prev) {
     this.curr = curr;
     this.prev = prev;
   }
}

并使用它来填充您的队列。当您找到目标 Node 时，使用 prev 字段跟踪路径，直到到达空 prev.

Java: 在二维矩阵中打印最短路径的有效方法

Java: Efficient way to print shortest path in 2d Matrix

java

algorithm

graph

matrix

shortest-path