题目

题面参考：https://leetcode.ca/2017-04-18-505-The-Maze-II/

/**
 * heap optimize
 */

public class Solution {
    /**
     * @param maze: the maze
     * @param start: the start
     * @param destination: the destination
     * @return: the shortest distance for the ball to stop at the destination
     */

    final int INF = 0x3f3f3f3f;
    final int[] dx = {0, -1, 0, 1}, dy = {-1, 0, 1, 0};
    boolean[][] st;
    int[][] distance;
    int n, m;
    PriorityQueue<int[]> heap;

    {
        heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);
    }

    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        n = maze.length;
        m = maze[0].length;

        st = new boolean[n][m];
        distance = new int[n][m];

        for(int i = 0; i < n; i++) {
            Arrays.fill(distance[i], INF);
        }
        distance[start[0]][start[1]] = 0;

        dijkstra(maze, start);

        return distance[destination[0]][destination[1]] == INF ? -1 : distance[destination[0]][destination[1]];
    }

    void dijkstra(int[][] maze, int[] start) {
        heap.offer(new int[]{start[0], start[1], 0});

        while(heap.size() > 0) {
            int[] t = heap.poll();
            int x = t[0], y = t[1], dist = t[2];

            if(st[x][y]) {
                continue;
            }
            st[x][y] = true;

            for(int i = 0; i < 4; i++) {
                int count = 0;
                x = t[0];
                y = t[1];
                while(true) {
                    int a = x + dx[i], b = y + dy[i];
                    if(a >= 0 && a < n && b >= 0 && b < m && maze[a][b] == 0) {
                        x = a;
                        y = b;
                        count++;
                    }
                    else break;
                }

                if(count > 0 && dist + count < distance[x][y]) {
                    distance[x][y] = dist + count;
                    heap.offer(new int[]{x, y, distance[x][y]});
                }
            }
        }
    }
}