# Share my easy Java solution with comments

• 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;
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){