505. The Maze II

class Solution {
    // 带权图
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int[][] distance = new int[maze.length][maze[0].length];
        for (int i = 0; i < distance.length; i++) {
            for (int j = 0; j < distance[0].length; j++) {
                distance[i][j] = Integer.MAX_VALUE;
            }
        }
        distance[start[0]][start[1]] = 0;
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(start);
        int[][] dirs = {`{-1, 0}, {1, 0}, {0, -1}, {0, 1}`};
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] dir : dirs) {
                int curDistance = 1;
                int x = cur[0] + dir[0];
                int y = cur[1] + dir[1];
                while (x >= 0 && x <= maze.length - 1 
                       && y >= 0 && y <= maze[0].length - 1 
                       && maze[x][y] == 0) {
                    x = x + dir[0];
                    y = y + dir[1];
                    curDistance ++;
                }
                x = x - dir[0];
                y = y - dir[1];
                curDistance --;

                if (distance[cur[0]][cur[1]] + curDistance < distance[x][y]) {
                    queue.offer(new int[]{x, y});
                    distance[x][y] = distance[cur[0]][cur[1]] + curDistance;
                } 
            }
        }
        return distance[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : distance[destination[0]][destination[1]];
    }
}