Java BFS Solution

• ``````    public class Square {
int i;
int j;
String building;
public Square(int i, int j, String building) {
this.i = i;
this.j = j;
this.building = building;
}

}

public int shortestDistance(int[][] grid) {
if (grid.length == 0 || grid[0].length == 0) return -1;
Map[][] stores = new Map[grid.length][grid[0].length];
int buildingCount = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
String name = i + " " + j;
buildingCount++;
q.add(new Square(i - 1, j, name));
q.add(new Square(i + 1, j, name));
q.add(new Square(i, j - 1, name));
q.add(new Square(i, j + 1, name));
}
}
}
int steps = 0;
boolean terminate = false;
int result = Integer.MAX_VALUE;
while (!q.isEmpty()) {
int count = q.size();
steps++;
while (count-- > 0) {
Square sq = q.poll();
int i = sq.i;
int j = sq.j;
String name = sq.building;
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != 0) continue;
if (stores[i][j] == null) stores[i][j] = new HashMap<>();
if (stores[i][j].containsKey(name)) continue;
stores[i][j].put(name, steps);
if (buildingCount == stores[i][j].size()) {
int res = 0;
for (Object n : stores[i][j].keySet()){
res += (Integer) stores[i][j].get(n);
}
result = Math.min(res, result);
}
q.add(new Square(i - 1, j, name));
q.add(new Square(i + 1, j, name));
q.add(new Square(i, j - 1, name));
q.add(new Square(i, j + 1, name));
}
}
return result == Integer.MAX_VALUE ? -1 : result;
}
}``````

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