## Shortest Distance from All Buildings

• Time:O(m^2n^2)
• Space:O(mn)

## C++

``````class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
const int nBuildings = getBuildingCount(grid);
const vector<int> dirs{0, 1, 0, -1, 0};
int ans = INT_MAX;
// dist[i][j] := total distance of grid[i][j] (0) to reach all buildings (1)
vector<vector<int>> dist(m, vector<int>(n));
// reachCount[i][j] := # of buildings (1) grid[i][j] (0) can reach
vector<vector<int>> reachCount(m, vector<int>(n));

auto bfs = [&](int row, int col) -> bool {
queue<pair<int, int>> q{{{row, col}}};
vector<vector<bool>> seen(m, vector<bool>(n));
seen[row][col] = true;
int depth = 0;
int seenBuildings = 1;

while (!q.empty()) {
++depth;
for (int sz = q.size(); sz > 0; --sz) {
const auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
const int x = i + dirs[k];
const int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (seen[x][y])
continue;
seen[x][y] = true;
if (!grid[x][y]) {
dist[x][y] += depth;
++reachCount[x][y];
q.emplace(x, y);
} else if (grid[x][y] == 1) {
++seenBuildings;
}
}
}
}

return seenBuildings == nBuildings;
};

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 1)  // bfs from this building
if (!bfs(i, j))
return -1;

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (reachCount[i][j] == nBuildings)
ans = min(ans, dist[i][j]);

return ans == INT_MAX ? -1 : ans;
}

private:
int getBuildingCount(vector<vector<int>>& grid) {
return accumulate(begin(grid), end(grid), 0, [](int s, vector<int>& row) {
return s + count(begin(row), end(row), 1);
});
}
};
``````

## JAVA

``````class Solution {
public int shortestDistance(int[][] grid) {
final int m = grid.length;
final int n = grid[0].length;
final int nBuildings = getBuildingCount(grid);
int ans = Integer.MAX_VALUE;
// dist[i][j] := total distance of grid[i][j] (0) to reach all buildings (1)
int[][] dist = new int[m][n];
// reachCount[i][j] := # of buildings (1) grid[i][j] (0) can reach
int[][] reachCount = new int[m][n];

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 1) // bfs from this building
if (!bfs(grid, i, j, dist, reachCount, nBuildings))
return -1;

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (reachCount[i][j] == nBuildings)
ans = Math.min(ans, dist[i][j]);

return ans == Integer.MAX_VALUE ? -1 : ans;
}

private static final int[] dirs = {0, 1, 0, -1, 0};

private boolean bfs(int[][] grid, int row, int col, int[][] dist, int[][] reachCount,
int nBuildings) {
final int m = grid.length;
final int n = grid[0].length;

Queue<int[]> q = new ArrayDeque<>(Arrays.asList(new int[] {row, col}));
boolean[][] seen = new boolean[m][n];
seen[row][col] = true;
int depth = 0;
int seenBuildings = 1;

while (!q.isEmpty()) {
++depth;
for (int sz = q.size(); sz > 0; --sz) {
final int i = q.peek()[0];
final int j = q.poll()[1];
for (int k = 0; k < 4; ++k) {
final int x = i + dirs[k];
final int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (seen[x][y])
continue;
seen[x][y] = true;
if (grid[x][y] == 0) {

dist[x][y] += depth;
++reachCount[x][y];
q.offer(new int[] {x, y});
} else if (grid[x][y] == 1) {
++seenBuildings;
}
}
}
}

return seenBuildings == nBuildings;
}

private int getBuildingCount(int[][] grid) {
int buildingCount = 0;
for (int[] row : grid)
for (final int cell : row)
if (cell == 1)
++buildingCount;
return buildingCount;
}
}
``````

## Python

``````class Solution:
def shortestDistance(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
dirs = [0, 1, 0, -1, 0]
nBuildings = sum(a == 1 for row in grid for a in row)
ans = math.inf
# dist[i][j] := total distance of grid[i][j] (0) to reach all buildings (1)
dist = [[0] * n for _ in range(m)]
# reachCount[i][j] := # of buildings (1) grid[i][j] (0) can reach
reachCount = [[0] * n for _ in range(m)]

def bfs(row: int, col: int) -> bool:
q = deque([(row, col)])
seen = {(row, col)}
depth = 0
seenBuildings = 1

while q:
depth += 1
for _ in range(len(q)):
i, j = q.popleft()
for k in range(4):
x = i + dirs[k]
y = j + dirs[k + 1]
if x < 0 or x == m or y < 0 or y == n:
continue
if (x, y) in seen:
continue
if not grid[x][y]:
dist[x][y] += depth
reachCount[x][y] += 1
q.append((x, y))
elif grid[x][y] == 1:
seenBuildings += 1

# True if all buildings (1) are connected
return seenBuildings == nBuildings

for i in range(m):
for j in range(n):
if grid[i][j] == 1:  # bfs from this building
if not bfs(i, j):
return -1

for i in range(m):
for j in range(n):
if reachCount[i][j] == nBuildings:
ans = min(ans, dist[i][j])

return -1 if ans == math.inf else ans
``````