# 0317. Shortest Distance from All Buildings
###### tags: `Leetcode` `Hard` `BFS`
Link: https://leetcode.com/problems/shortest-distance-from-all-buildings/
## 思路 $O(M^2N^2)$ $O(MN)$
从每个building开始搜起，对于位于(i,j)的building，做bfs，算出每个empty land到这个building的距离，然后跟之前算出来的距离求和放进dist里，同时要计算出每个empty land能到达几个building
最后做完bfs之后，找能到达所有empty land的点，找出他们的dist最小值就是答案
## Code

class Solution {
    public int shortestDistance(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n];
        int[][] reach = new int[m][n];
        int[][] dirs = new int[][]{{0,1},{1,0},{-1,0},{0,-1}};
        int buildingNum = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]==0 || grid[i][j]==2) continue;
                buildingNum++;
                boolean[][] visited = new boolean[m][n];
                visited[i][j] = true;
                Queue<int[]> q = new LinkedList<>();
                q.add(new int[]{i,j});
                int d = 0;
                while(!q.isEmpty()){
                    int size = q.size();
                    for(int k=0; k<size; k++){
                        int[] curr = q.poll();
                        dist[curr[0]][curr[1]] += d;
                        reach[curr[0]][curr[1]] += 1;
                        for(int[] dir:dirs){
                            int nextx = curr[0]+dir[0];
                            int nexty = curr[1]+dir[1];
                            if(nextx>=0 && nextx<m && nexty>=0 && nexty<n && !visited[nextx][nexty] && grid[nextx][nexty]==0){
                                q.add(new int[]{nextx, nexty});
                                visited[nextx][nexty] = true;
                            }
                        }
                    }
                    d++;
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]==0 && reach[i][j]==buildingNum){
                    ans = Math.min(ans, dist[i][j]);
                }
            }
        }
        return ans==Integer.MAX_VALUE?-1:ans;
    }
}