505. The Maze II (spfa

BFS use queue

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

class Solution {
    int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int m = maze.length;
        int n = maze[0].length;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(start);
        
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        dist[start[0]][start[1]] = 0;
        
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            
            // cant stop here, there is maybe a better result in the future, dijkstra may stop here
            // if (cur[0] == destination[0] && cur[1] == destination[1]) {
            //     return dist[destination[0]][destination[1]];
            // }
            
            for (int[] dir : dirs) {
                int x = cur[0];
                int y = cur[1];
                
                int steps = 0;
                while (isValid(maze, x+dir[0], y+dir[1])) {
                    x += dir[0];
                    y += dir[1];
                    steps++;
                }
                int newDist = dist[cur[0]][cur[1]] + steps;
                if (newDist < dist[x][y]) {
                    queue.offer(new int[]{x, y});
                    dist[x][y] = newDist;
                }
            }
        }
        int result = dist[destination[0]][destination[1]];
        
        return result == Integer.MAX_VALUE ? -1 : result;
    }
    private boolean isValid(int[][] maze, int x, int y) {
        return x >= 0 && x < maze.length && y >= 0 && y < maze[0].length 
            && maze[x][y] == 0;
    }
}

use PQ

class Solution {
    int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    class State {
        int[] points;
        int dist;
        State(int[] points, int dist) {
            this.points = points;
            this.dist = dist;
        }
    }
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int m = maze.length;
        int n = maze[0].length;
        
        // use PriorityQueue
        Queue<State> queue = new PriorityQueue<>((a, b) -> a.dist - b.dist);
        queue.offer(new State(start, 0));
        
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        dist[start[0]][start[1]] = 0;
        
        while (!queue.isEmpty()) {
            State cur = queue.poll();
            
            // cant stop here, there is maybe a better result in the future, dijkstra may stop here
            // if (cur[0] == destination[0] && cur[1] == destination[1]) {
            //     return dist[destination[0]][destination[1]];
            // }
            
            for (int[] dir : dirs) {
                int x = cur.points[0];
                int y = cur.points[1];
                int curDist = cur.dist;
                
                int steps = 0;
                while (isValid(maze, x+dir[0], y+dir[1])) {
                    x += dir[0];
                    y += dir[1];
                    steps++;
                }
                int newDist = curDist + steps;
                if (newDist < dist[x][y]) {
                    queue.offer(new State(new int[]{x, y}, newDist));
                    dist[x][y] = newDist;
                }
            }
        }
        int result = dist[destination[0]][destination[1]];
        
        return result == Integer.MAX_VALUE ? -1 : result;
    }
    private boolean isValid(int[][] maze, int x, int y) {
        return x >= 0 && x < maze.length && y >= 0 && y < maze[0].length 
            && maze[x][y] == 0;
    }
}