Simple Java solution and no priority queue beats 90%


  • 0
    M

    I did not use priority queue and just use a 2D distance array to record the minimum distance to reach here. It beats 90%. The idea is only the shortest path can get to next search iteration.

    private final static int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            if (maze == null) return 0;
            // bfs
            int m = maze.length;
            int n = maze[0].length;
            int[][] dist = new int[m][n]; /* record the minimum distance to reach here */
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    dist[i][j] = Integer.MAX_VALUE;
                }
            }
            
            dist[start[0]][start[1]] = 0;
            Queue<int[]> queue = new LinkedList<>();
            queue.add(new int[]{start[0], start[1]});
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int[] curStop = queue.poll();
                    for (int[] dir : dirs) {
                        int x = curStop[0] + dir[0];
                        int y = curStop[1] + dir[1];
                        while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] != 1) {
                            x += dir[0];
                            y += dir[1];
                        }
                        //go back one step
                        x -= dir[0];
                        y -= dir[1];
                        if (x == curStop[0] && y== curStop[1]) continue;
                        int distFromLast = Math.abs(x - curStop[0]) + Math.abs(y - curStop[1]);
                        if (distFromLast + dist[curStop[0]][curStop[1]] < dist[x][y]) {
                            dist[x][y] = dist[curStop[0]][curStop[1]] + distFromLast;
                            queue.add(new int[]{x, y});
                        }
                    }
                }
            }
            
            return dist[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : dist[destination[0]][destination[1]];
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.