java solution using priority first search


  • 0
    2
    public class Solution {
        
        private static final int[][] increments = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
        
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            boolean[][] isVisited = new boolean[maze.length][maze[0].length];
            Queue<Coordinate> q = new PriorityQueue<>();
            q.add(new Coordinate(0, start));
            while (!q.isEmpty()) {
                Coordinate c = q.remove();
                if (Arrays.equals(c.point, destination)) {
                    return c.priority;
                }
                if (isVisited[c.point[0]][c.point[1]]) {
                    continue;
                }
                isVisited[c.point[0]][c.point[1]] = true;
                for (int[] increment : increments) {
                    int priority = c.priority;
                    int[] point = c.point;
                    while (true) {
                        int[] next = {point[0] + increment[0], point[1] + increment[1]};
                        if (next[0] < 0 || next[0] >= maze.length || next[1] < 0 || next[1] >= maze[0].length || maze[next[0]][next[1]] == 1) {
                            break;
                        }
                        priority++;
                        point = next;
                    }
                    q.add(new Coordinate(priority, point));
                }
            }
            return -1;
        }
        
        private class Coordinate implements Comparable<Coordinate> {
            final int priority;
            final int[] point;
            
            public Coordinate(int priority, int[] point) {
                this.priority = priority;
                this.point = point;
            }
            
            @Override
            public int compareTo(Coordinate that) {
                return Integer.compare(this.priority, that.priority);
            }
        }
    }
    

Log in to reply
 

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