Shortest Distance from All Buildings

Hard

You are given a grid where 0 is empty land you can travel through, 1 marks a building, and 2 marks an obstacle. Return the shortest total travel distance from an empty land cell that can reach all buildings (moving 4-directionally). If no such cell exists, return -1.

Example 1

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

Example 2

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

Example 3

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

Constraints

• 1 <= m, n <= 50
• grid[i][j] is 0, 1, or 2
• There is at least one building.