# BFS method with pruning, JAVA, Good performance

• ``````/*
* Aim:
* Among all empty lands accessible by all buildings, find the one which has the smallest sum of distances
* Two subproblems, calculate distance and accessibility.
*
* Method:
* For each building in the grid, use BFS to update its distance to all empty lands accessible from it.
* Maintain a "map" matrix to save the sum of distances from all buildings to a certain empty land.
* e.g. the distance between buildingA and empty spot(x, y) is disA, the distance between
* buildingB and empty spot(x, y) is disB. Then, map[x, y] = disA + disB;
* The smallest travel distance is the smallest value in the map which is accessible by all buildings.
*
* Improvement: inspired by @StefanPochmann's idea :"Instead, I walk only onto the cells that were reachable from all previous buildings. From the first building I only walk onto cells where grid is 0, and make them -1. From the second building I only walk onto cells where grid is -1, and I make them -2. And so on."
* When updating the ith building's distance to all empty spaces, consider only positions which are accessible by all the previous i-1 buildings.
*
* Sum up :
* n is the entry number of input matrix.
* Time O(n2) : Space O(n)
*
* real performance: 11ms
*/
public class Solution {
public int shortestDistance(int[][] grid) {
int height = grid.length;
int width = grid[0].length;
int[][] map = new int[height][width];
int b_cnt = 0;
int[] steps = {1, 0, -1, 0, 1};
for (int i = 0; i < height; i ++) {
for (int j = 0; j < width; j ++) {
if (grid[i][j] == 1) {
if (!BFS(b_cnt, grid, map, new boolean[height][width], i, j, steps) {
return -1;
}
b_cnt --;
}
}
}
int Shortest = Integer.MAX_VALUE;
for (int i = 0; i < height; i ++) {
for (int j = 0; j < width; j ++) {
if (grid[i][j] == b_cnt && Shortest > map[i][j]) {
Shortest = map[i][j];
}
}
}
return Shortest == Integer.MAX_VALUE ? -1 : Shortest;
}

public boolean BFS(int b_cnt, int[][] grid, int[][] map, boolean[][] visited, int row, int col, int[] steps) {
int distance = 1;
List<Integer> curr = new ArrayList<>();
boolean valid = false;
while (!curr.isEmpty()) {
List<Integer> next = new ArrayList<>();
int size = curr.size();
for (int i = 0; i < size; i += 2) {
int r = curr.get(i);
int c = curr.get(i + 1);
for (int k = 1; k < steps.length; k ++) {
int x = r + steps[k - 1];
int y = c + steps[k];
if (x >= 0 && x <  map.length && y >= 0 && y < map[0].length && !visited[x][y] && grid[x][y] == b_cnt) {
valid = true;
visited[x][y] = true;
grid[x][y] --;
map[x][y] += distance;
}
}
}
curr = next;
distance ++;
}
return valid;
}
}

``````

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