499. The Maze III

Version #1 Dijastra

几个需要注意的点
首先visited是必须要有的，否则impossible就是infinite loop
但是不应该是个boolean而应该是一个int，因为一个点可以通过不同的path被到达，只要后来的dist <= visited[ny][nx]都可以
因为hole不一定是球可以停住的状态，所以第一次经过不一定是最佳答案
需要存起来然后每次经过的话都去更新

 73.91 %
class Solution {
    class Point implements Comparable<Point> {
        int x, y, dist;
        String path;
        public Point(int y, int x, int dist, String path) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.path = path;
        }
        @Override
        public int compareTo(Point p) {
            if (this.dist != p.dist) {
                return this.dist - p.dist;
            } else {
                return this.path.compareTo(p.path);
            }
        }
    }
    private int rows, cols;
    private int[] dx = new int[]{1, 0, -1, 0};
    private int[] dy = new int[]{0, -1, 0, 1};
    private char[] direction = new char[]{'r', 'u', 'l', 'd'};
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        // priorityQueue of int[] poisition + int dist so far
        // when we pop one element out, we have four choices
        // 1.minHeap ordered by dist
        // 2.original point into minHeap
        // polling from minHeap, try 4 directions and walk
        // if we can walk to that direction (move more than 0 step, destination not visited)
        // if we see hole while rolling, return the final steps directly
        // offer into minHeap with destination position and new distance
       
        if (maze == null || maze.length == 0 || maze[0] == null || maze[0].length == 0) {
            return "impossible";
        }
        PriorityQueue<Point> minHeap = new PriorityQueue<>();
        rows = maze.length;
        cols = maze[0].length;
        int[][] visited = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        minHeap.offer(new Point(ball[0], ball[1], 0, ""));
        visited[ball[0]][ball[1]] = 0;
        Point minResult = null;
        while (!minHeap.isEmpty()) {
            Point curr = minHeap.poll();
            int x = curr.x;
            int y = curr.y;
            int dist = curr.dist;
            if (minResult != null && dist > minResult.dist) break;
            String path = curr.path;
            for (int i = 0; i < 4; i++) {
                // try to roll to direction
                int step = 0;
                int nx = x, ny = y;
                while (isValid(ny + dy[i], nx + dx[i]) && maze[ny + dy[i]][nx + dx[i]] == 0) {
                    ny += dy[i];
                    nx += dx[i];
                    step++;
                    if (ny == hole[0] && nx == hole[1]) {
                        Point temp = new Point(ny, nx, dist + step, path + direction[i]);
                        if (minResult == null || temp.compareTo(minResult) < 0) {
                            minResult = temp;
                        }
                    }
                }
                if (step > 0 && dist + step <= visited[ny][nx]) {
                    visited[ny][nx] = dist + step;
                    minHeap.offer(new Point(ny, nx, dist + step, path + direction[i]));
                }
               
            }
        }
        return minResult == null ? "impossible" : minResult.path;
    }
   
    private boolean isValid(int y, int x) {
        return x >= 0 && x < cols && y >= 0 && y < rows;
    }
}