# 317. Shortest Distance from All Buildings

![](/files/-MeK3cguEzslvemCr_Xi)

![](/files/-MeK3fc8_bIDECaKhIRC)

![](/files/-MeK3kDdRMy6OnZwPBXb)

You want to build a house on an empty land that **reaches all buildings** in the **shortest** total travel distance.

#### 所以要從每個 1 出發去做 bfs, 建構出最小的距離（**reaches all buildings 的總距離）**

####

#### 所以需要兩個表:

dist: 總距離表

nums: 可以到幾個建築物, 因為最後計算我們只要能到 **reaches all buildings 的點,** 

**nums\[i]\[j] 如果數量 =  all buildings 數量, 才是可以蓋房子的空地, 從這裡面找距離最小的**

#### bfs part: 

跟往常寫法一樣, 裡面內涵一個 visited\[]\[], 每次跑bfs都會重置, 判斷border

全部跑完後, 最後來找最小距離 (**reaches all buildings**), 找不到回 -1

time: O(m\*n\*BFS) = O(m^2\*n^2)

space: O(m\*n)

```java
class Solution {
    private static final int[][] DIRECTIONS = new int[][]{{1,0}, {0,1}, {-1,0}, {0,-1}};

    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0) return -1;
        int m = grid.length;
        int n = grid[0].length;
        int dist[][] = new int[m][n];
        int nums[][] = new int[m][n];
        
        int buildingNums = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) { // node 1 do BFS
                    buildingNums++;
                    bfs(grid, i, j, dist, nums);
                }
            }
        }
        
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (buildingNums == nums[i][j] && grid[i][j] == 0 && dist[i][j] != 0) {
                    res = Math.min(res, dist[i][j]);
                }
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
    
    
    private void bfs(int[][] grid, int row, int col, int[][] dist, int[][] nums) {
        int m = grid.length;
        int n = grid[0].length;
        
        boolean visited[][] = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        
        queue.offer(new int[]{row, col});
        visited[row][col] = true;
        
        int distance = 0;
        while (!queue.isEmpty()) {
            distance++;
            int size = queue.size();
            for (int q = 0; q < size; q++) {
                int cell[] = queue.poll();
                for (int dir[] : DIRECTIONS) {
                    int x = cell[0] + dir[0];
                    int y = cell[1] + dir[1];
                    if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y] && grid[x][y] == 0) {
                        visited[x][y] = true;
                        queue.offer(new int[]{x, y});
                        dist[x][y] += distance;
                        nums[x][y]++;
                    }
                }
            }
        }
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/317.-shortest-distance-from-all-buildings.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.