# 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 the idea of traversing the maze.

Need to use the 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, 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 The 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