Simple Java Solution BFS


  • 1
    D
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            Queue<int[]> q = new LinkedList<>();
            int m = maze.length, n = maze[0].length;
            int[][] dist = new int[m][n];
            for (int i = 0; i < m; i++) {
                Arrays.fill(dist[i], Integer.MAX_VALUE);
            }
            int[] dx = new int[] {-1, 0, 1, 0};
            int[] dy = new int[] { 0, 1, 0, -1};
            
            q.offer(start);
            dist[start[0]][start[1]] = 0;
            
            while (!q.isEmpty()) {
                int[] p = q.poll();
                for (int i = 0; i < 4; i++) {
                    int x = p[0] + dx[i], y = p[1] + dy[i];
                    int cnt = 1;
                    
                    while (x >=0 && x < m && y >= 0 && y < n && maze[x][y] != 1) {
                        x += dx[i];
                        y += dy[i];
                        cnt++;
                    }
                    x -= dx[i];
                    y -= dy[i];
                    cnt--;
                    if (dist[p[0]][p[1]] + cnt < dist[x][y]) {
                        dist[x][y] = dist[p[0]][p[1]] + cnt;
                        q.offer(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.