499. The Maze III (spfa, dijkstra

this is good to read

https://leetcode.com/problems/the-maze-iii/discuss/1349818/Java-PriorityQueue-and-BFS

T: O(mn)
S: O(mn)

class Solution {
    int[][] dirs = {{-1,0},{0,1},{1,0},{0,-1}};
    String[] dirsStr = {"u","r","d","l"};
    class State implements Comparable<State>{
        int x;
        int y;
        int dist;
        String path;
        State(int x, int y, int dist, String path) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.path = path;
        }
        State(int x, int y) {
            this.x = x;
            this.y = y;
            this.dist = Integer.MAX_VALUE;
            this.path = "";
        }
        public int compareTo(State p) {
            return this.dist == p.dist ? this.path.compareTo(p.path) : this.dist - p.dist;
        }
    }

    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        int m = maze.length;
        int n = maze[0].length;

        
        State[][] dist = new State[m][n];
        for (int i = 0; i < m * n; i++) {
            dist[i / n][i % n] = new State(i / n, i % n);
        }
//         dist[ball[0]][ball[1]] = new State(ball[0], ball[1], 0, ""); dont need, why

        PriorityQueue<State> queue = new PriorityQueue<>(); // using priority queue
        queue.offer(new State(ball[0], ball[1], 0, ""));
        
        while (!queue.isEmpty()) {
            State cur = queue.poll();
            
            if (dist[cur.x][cur.y].compareTo(cur) <= 0) {
                continue;
            }
            dist[cur.x][cur.y] = cur;

            for (int i = 0; i < dirs.length; i++) {
                int[] dir = dirs[i];
                String newPath = dirsStr[i];

                int x = cur.x;
                int y = cur.y;
                int curDist = cur.dist;
                String curPath = cur.path;

                int steps = 0;
                // because when meet hole, while end, so we still need hole case
                while (isValid(maze, x, y, hole)) { 
                    x += dir[0];
                    y += dir[1];
                    steps++;
                }
                if (x != hole[0] || y != hole[1]) { // check the hole
                    x -= dir[0];
                    y -= dir[1];
                    steps--;
                }
                
                State next = new State(x, y, curDist + steps, curPath + newPath);
                queue.offer(next);
            }
        }
                
        return dist[hole[0]][hole[1]].dist == Integer.MAX_VALUE ? "impossible" : dist[hole[0]][hole[1]].path;
    }
    private boolean isValid(int[][] maze, int x, int y, int[] hole) {
        return x >= 0 && x < maze.length && y >= 0 && y < maze[0].length 
            && maze[x][y] == 0 && (x != hole[0] || y != hole[1]);
    }
}

dijkstra

class Solution {
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        PriorityQueue<Point> pq = new PriorityQueue<>((a, b) -> a.distance == b.distance ? a.movement.compareTo(b.movement) : a.distance - b.distance);
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        char[] move = {'d', 'u', 'r', 'l'};
        pq.offer(new Point(ball[0], ball[1], 0, ""));
        
        while (!pq.isEmpty()) {
            Point point = pq.poll();
            
            if (point.row == hole[0] && point.col == hole[1])
                return point.movement;
            
            visited[point.row][point.col] = true;

            for (int i = 0; i < 4; i++) {
                int[] dir = dirs[i];
                int row = point.row;
                int col = point.col;
                int distance = point.distance;
                
                while (isValid(maze, row + dir[0], col + dir[1])) {
                    row += dir[0];
                    col += dir[1];
                    distance++;
                    
                    if (row == hole[0] && col == hole[1])
                        break;
                }

                if (!visited[row][col])
                    pq.offer(new Point(row, col, distance, point.movement + move[i]));
            }
        }
        
        return "impossible";
    }
    
    boolean isValid(int[][] maze, int row, int col) {
        if (row < 0 || row >= maze.length || col < 0 || col >= maze[0].length || maze[row][col] == 1)
            return false;
        return true;
    }
    
    class Point {
        int row, col, distance;
        String movement;
        
        Point(int row, int col, int distance, String movement) {
            this.row = row;
            this.col = col;
            this.distance = distance;
            this.movement = movement;
        }
    }
}