# Question

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

You are given an m x n grid grid of values 0, 1, or 2, where:

• each 0 marks an empty land that you can pass by freely,
• each 1 marks a building that you cannot pass through, and
• each 2 marks an obstacle that you cannot pass through.

You want to build a house on an empty land that reaches all buildings in the shortest total travel distance. You can only move up, down, left, and right.

Return the shortest travel distance for such a house. If it is not possible to build such a house according to the above rules, return -1.

The total travel distance is the sum of the distances between the houses of the friends and the meeting point.

The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Example 1:

Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2).
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.


Example 2:

Input: grid = [[1,0]]
Output: 1


Example 3:

Input: grid = [[1]]
Output: -1


Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] is either 0, 1, or 2.
• There will be at least one building in the grid.

# 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

• 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[0].length == 0) {
return 0;
}

int m = grid.length, n = grid[0].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[0].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(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int total = 0;
int[][] cnt = new int[m][n];
int[][] dist = new int[m][n];
int[] dirs = {-1, 0, 1, 0, -1};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
++total;
q.offer(new int[] {i, j});
int d = 0;
boolean[][] vis = new boolean[m][n];
while (!q.isEmpty()) {
++d;
for (int k = q.size(); k > 0; --k) {
int[] p = q.poll();
for (int l = 0; l < 4; ++l) {
int x = p[0] + dirs[l];
int y = p[1] + dirs[l + 1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0
&& !vis[x][y]) {
++cnt[x][y];
dist[x][y] += d;
q.offer(new int[] {x, y});
vis[x][y] = true;
}
}
}
}
}
}
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 0 && cnt[i][j] == total) {
ans = Math.min(ans, dist[i][j]);
}
}
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
}

• class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
int res = INT_MAX, buildingCnt = 0, m = grid.size(), n = grid[0].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][0], y = b + dirs[k][1];
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;
}
};

• class Solution:
def shortestDistance(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
q = deque()
total = 0 # total building count
# cnt: how many buildings can reach (x,y)
#      if there is a column all blockers, then (x,y) cannot reach every building
cnt = [[0] * n for _ in range(m)]
dist = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
total += 1
q.append((i, j))
d = 0
vis = set() # reset for every free-land
while q:
d += 1
for _ in range(len(q)):
r, c = q.popleft()
for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
x, y = r + a, c + b
if (
0 <= x < m
and 0 <= y < n
and grid[x][y] == 0
and (x, y) not in vis
):
cnt[x][y] += 1
dist[x][y] += d
q.append((x, y))
ans = inf
for i in range(m):
for j in range(n):
if grid[i][j] == 0 and cnt[i][j] == total:
ans = min(ans, dist[i][j])
return -1 if ans == inf else ans

############

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[0]) 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[0])):
if grid[i][j] == 1:
count += 1

hit = [[0] * len(grid[0]) for _ in range(0, len(grid))]
for i in range(0, len(grid)):
for j in range(0, len(grid[0])):
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[0])):
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


• func shortestDistance(grid [][]int) int {
m, n := len(grid), len(grid[0])
var q [][]int
total := 0
cnt := make([][]int, m)
dist := make([][]int, m)
for i := range cnt {
cnt[i] = make([]int, n)
dist[i] = make([]int, n)
}
dirs := []int{-1, 0, 1, 0, -1}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
total++
q = append(q, []int{i, j})
vis := make([]bool, m*n)
d := 0
for len(q) > 0 {
d++
for k := len(q); k > 0; k-- {
p := q[0]
q = q[1:]
for l := 0; l < 4; l++ {
x, y := p[0]+dirs[l], p[1]+dirs[l+1]
if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0 && !vis[x*n+y] {
cnt[x][y]++
dist[x][y] += d
q = append(q, []int{x, y})
vis[x*n+y] = true
}
}
}
}
}
}
}

ans := math.MaxInt32
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 0 && cnt[i][j] == total {
if ans > dist[i][j] {
ans = dist[i][j]
}
}
}
}
if ans == math.MaxInt32 {
return -1
}
return ans
}