单元最短路径问题贪心Java

单元最短路径问题是指在一个网格图中，从起点到终点的最短路径，其中每一步只能向上、下、左、右四个方向走。这个问题可以使用贪心算法来解决。

具体的贪心策略是，每次走一步时，都选择能够到达终点的方向中距离终点最近的方向。这样每次都朝着终点“靠拢”，就可以找到最短路径。

Java代码实现：

public class ShortestPath {
    public int shortestPath(int[][] grid) {
        int m = grid.length;
        int n = grid.length;
        int[][] distance = new int[m][n];
        for (int[] row : distance) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        distance[0] = grid;
        boolean[][] visited = new boolean[m][n];
        int[] dx = {0, 0, -1, 1, 0, 0};
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a - b);
        pq.offer(new int[]{0, 0, grid});
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int x = curr;
            int y = curr;
            int dist = curr;
            if (visited[x][y]) {
                continue;
            }
            visited[x][y] = true;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && dist + grid[nx][ny] < distance[nx][ny]) {
                    distance[nx][ny] = dist + grid[nx][ny];
                    pq.offer(new int[]{nx, ny, distance[nx][ny]});
                }
            }
        }
        return distance[m - 1][n - 1];
    }
}