# Java 36ms BFS from each building, cumulate cost for each empty space

• See code with comments below. Two tips for the cost[][] matrix

1. cost == -1 marks unreachable empty space from previous BFS, so that it can be skipped in the current BFS; 2. cost == 0 are nodes not yet visited in the current BFS. If it remains 0 after the BFS is finished, reassign it as cost = -1

public class Solution {

``````public int shortestDistance(int[][] grid) {
// assuming that empty lands far outnumber buildings, do BFS from each
// building and update a matrix which records total distance from each
// empty land to all buildings, find the min
// complexity: O(B(V+E) + V) where B is the number of buildings
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
return -1;
}
int m = grid.length;
int n = grid[0].length;
int[][] cost = new int[m][n]; // BFS cost starting from each building
int[][] totalCost = new int[m][n]; // cumulative cost
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
// BFS from building to all empty spaces
BFS(grid, cost, i, j);
// reset state for visited empty spaces
// also mark the unreachable empty spaces
// s.t. they won't be further considered
for (int ii = 0; ii < m; ii++) {
for (int jj = 0; jj < n; jj++) {
if (grid[ii][jj] == 0) {
if (cost[ii][jj] > 0) {
totalCost[ii][jj] += cost[ii][jj];
cost[ii][jj] = 0;
} else {
cost[ii][jj] = -1;
totalCost[ii][jj] = Integer.MAX_VALUE;
}
}
}
}
}
}
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
min = Math.min(min, totalCost[i][j]);
}
}
}
return min == Integer.MAX_VALUE ? -1 : min;
}

private void BFS(int[][] grid, int[][] cost, int i, int j) {
queue.offerLast(new int[]{i, j});
cost[i][j] = 0;
while (!queue.isEmpty()) {
int[] curr = queue.pollFirst();
int[][] moves = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
for (int[] m : moves) {
int iprime = curr[0] + m[0];
int jprime = curr[1] + m[1];
if (iprime >= 0 && iprime < grid.length &&
jprime >= 0 && jprime < grid[0].length &&
grid[iprime][jprime] == 0 &&
cost[iprime][jprime] == 0) {
cost[iprime][jprime] = cost[curr[0]][curr[1]] + 1;
queue.offerLast(new int[]{iprime, jprime});
}
}
}
}
``````

}

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