Share my easy Java solution with comments


  • 0
    Q

    The basic idea is to use BFS starting from every possible empty cell filled with zero and get the minimum from all results, a Point class is created with attribute "steps" to track the steps or distance from starting point to current point. If the number of houses found in BFS is less than total number of house on grid, it means some houses are not reachable, in this case we simply return -1.

    public class Solution {
            private class Point {
                public int i;
                public int j;
                public int steps;
                public Point(int i, int j, int steps){
                    this.i = i;
                    this.j = j;
                    this.steps = steps;
                }    
            }
            
            public int shortestDistance(int[][] grid) {
                int height = grid.length, width = grid[0].length;
                int min = Integer.MAX_VALUE, houses = 0;
                // Count all existing houses in grid
                for(int i=0; i<height; i++){
                    for(int j=0; j<width; j++){
                        if(grid[i][j] == 1) houses++;
                    }
                }
                // Start from all empty cells one by one
                for(int i=0; i<height; i++){
                    for(int j=0; j<width; j++){
                        if(grid[i][j] == 0){
                            int sum = search(i, j, houses, grid);
                            min = Math.min(min, sum);
                        }
                    }
                }
                // Can't find all existing houses
                if(min == Integer.MAX_VALUE) return -1;
                else return min;
            }
            
            public int search(int i, int j, int houses, int[][] grid){
                int height = grid.length, width = grid[0].length;
                boolean[][] marked = new boolean[height][width];
                int houseCount = 0, sum = 0;
                Queue<Point> q = new LinkedList<>();
                q.add(new Point(i, j, 0));
                marked[i][j] = true;
                while(!q.isEmpty()){
                    Point point = q.poll();
                    // Traverse four surrounding cells
                    for(int m=-1; m<=1; m++){
                        for(int n=-1; n<=1; n++){
                            // Current point itself or out of boundary
                            if((Math.abs(m) == Math.abs(n)) || !(point.i+m >=0 && point.i+m<height && point.j+n>=0 && point.j+n<width) 
                            || marked[point.i+m][point.j+n]) 
                                continue;
                            int cell = grid[point.i+m][point.j+n];
                            // Find a unmarked house 
                            if(cell == 1){
                                houseCount++;
                                sum += point.steps+1;
                                marked[point.i+m][point.j+n] = true;
                            }
                            else if(cell == 0){
                                q.add(new Point(point.i+m, point.j+n, point.steps+1)); 
                                marked[point.i+m][point.j+n] = true;
                            }
                        }
                    }
                }
                // Can't find all existing houses
                if(houseCount < houses) return Integer.MAX_VALUE;
                else return sum;
            }
        }

Log in to reply
 

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