# Question

Formatted question description: https://leetcode.ca/all/317.html

 317	Shortest Distance from All Buildings

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance.
You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

Each 0 marks an empty land which you can pass by freely.
Each 1 marks a building which you cannot pass through.
Each 2 marks an obstacle which you cannot pass through.

For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (1,2) is an ideal empty land to build a house,
as the total travel distance of 3+3+1=7 is minimal. So return 7.

Note:
There will be at least one building.
If it is not possible to build such house according to the above rules, return -1.

@not-real-similar: 296	Best Meeting Point
@similar: 286	Walls and Gates


# Algorithm

In some cases, the obstacle completely blocks a certain building, then -1 should be returned. So this problem can only be solved by traversing the maze.

Need to use queue to traverse, we perform a BFS traversal of the whole picture for each building position, and establish a distance field of dist each time.

Since our BFS traversal needs to mark the locations that should be visited, and we don’t want to build a two-dimensional matrix of visits, then, what should we do, here is a small trick,

• When we first traverse, we always find the position of 0. After the traversal, we assign it to -1.
• In this way, in the next round of traversal, we will find the position of -1 and assign them all to -2,
• And so on until all buildings are traversed

Then update the values of dist and sum during the traversal process. Note that our dist is a local variable, and it is initialized to grid every time. The real distance field is accumulated in sum. Since the position of the building is 1 in the grid, dist initialization in the middle is also 1, and it needs to be subtracted by 1 when added to the sum.

We use the value in the sum to update the value of the result res, and finally see if we want to return -1 according to the value of result.

# Code

Java

• import java.util.LinkedList;
import java.util.Queue;

public class Shortest_Distance_from_All_Buildings {

public static void main(String[] args) {
Shortest_Distance_from_All_Buildings out = new Shortest_Distance_from_All_Buildings();
Solution s = out.new Solution();

System.out.println(s.shortestDistance(new int[][] { {1,0,2,0,1},{0,0,0,0,0},{0,0,1,0,0} } ));
}

public class Solution {
/**
* @param grid: the 2D grid
* @return: the shortest distance
*/
public int shortestDistance(int[][] grid) {
if (grid == null || grid.length == 0 || grid.length == 0) {
return 0;
}

int m = grid.length, n = grid.length;
int[][] totalDistance = new int[m][n];
int step = 0;
int res = 0;

for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
res = bfs(grid, i, j, step, totalDistance);
step--;
}
}
}

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

private int bfs(int[][] grid, int x, int y, int step, int[][] totalDistance) {
int res = Integer.MAX_VALUE;
int m = grid.length;
int n = grid.length;;

queue.offer(x * n + y);

int curDistance = 0;
int[] directions = {-1, 0, 1, 0, -1};

while (!queue.isEmpty()) {
int l = queue.size();
curDistance++;
while (l-- != 0) {
int t = queue.poll();
x = t / n; // restore. could also be a tuple(x,y) put in queue
y = t % n;

for (int i = 0; i < 4; ++i) {
int _x = x + directions[i], _y = y + directions[i + 1];
if (_x >= 0 && _x < m && _y >= 0 && _y < n && grid[_x][_y] == step) {
queue.offer(_x * n + _y);
totalDistance[_x][_y] += curDistance;
grid[_x][_y]--;
res = Math.min(res, totalDistance[_x][_y]);
}
}
}
}
return res;
}
}
}

• class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
int res = INT_MAX, buildingCnt = 0, m = grid.size(), n = grid.size();
vector<vector<int>> dist(m, vector<int>(n, 0)), cnt = dist;
vector<vector<int>> dirs{ {0,-1},{-1,0},{0,1},{1,0} };
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
++buildingCnt;
queue<pair<int, int>> q;
q.push({i, j});
vector<vector<bool>> visited(m, vector<bool>(n, false));
int level = 1;
while (!q.empty()) {
int size = q.size();
for (int s = 0; s < size; ++s) {
int a = q.front().first, b = q.front().second; q.pop();
for (int k = 0; k < dirs.size(); ++k) {
int x = a + dirs[k], y = b + dirs[k];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0 && !visited[x][y]) {
dist[x][y] += level;
++cnt[x][y];
visited[x][y] = true;
q.push({x, y});
}
}
}
++level;
}
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 0 && cnt[i][j] == buildingCnt) {
res = min(res, dist[i][j]);
}
}
}
return res == INT_MAX ? -1 : res;
}
};

• from collections import deque

class Solution(object):
def shortestDistance(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""

def bfs(si, sj, grid, buildNum, hit):
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
queue = deque([(si, sj, 0)])
visited = set([(si, sj)])
count = 1
while queue:
i, j, dist = queue.popleft()
for di, dj in dirs:
newi, newj = i + di, j + dj
if (newi, newj) in visited:
continue
if 0 <= newi < len(grid) and 0 <= newj < len(grid) and grid[newi][newj] != 2:
if grid[newi][newj] != 1:
grid[newi][newj] -= dist + 1
hit[newi][newj] += 1
visited |= {(newi, newj)}
queue.append((newi, newj, dist + 1))
else:
count += 1
visited |= {(newi, newj)}

if count != buildNum:
print
count, buildNum
return False
return True

count = 0
for i in range(0, len(grid)):
for j in range(0, len(grid)):
if grid[i][j] == 1:
count += 1

hit = [ * len(grid) for _ in range(0, len(grid))]
for i in range(0, len(grid)):
for j in range(0, len(grid)):
if grid[i][j] == 1:
if not bfs(i, j, grid, count, hit):
return -1

ans = float("-inf")
for i in range(0, len(grid)):
for j in range(0, len(grid)):
if grid[i][j] < 0 and hit[i][j] == count:
ans = max(ans, grid[i][j])
grid[i][j] = 0
return -ans if ans != float("-inf") else -1