https://leetcode.com/problems/shortest-distance-from-all-buildings/description/

image.png

这道题就是从K个房子每个BFS，求到各个空地的最短路径了。因为有障碍物我们没法MN了。只能KM*N。
还需要统计CNT,因为可能因为某些障碍物导致，一个房子完全没法到达另一个。
最后再遍历每个空地，看CNT是不是和房子数一样，如果一样更新MIN。
最后输出MIN就好了。

int h;
    int l;
    public int shortestDistance(int[][] grid) {
        h = grid.length;
        l = grid[0].length;
        int[][] dis = new int[h][l];
        int[][] cnt = new int[h][l];
        int min = Integer.MAX_VALUE;
        int maxCnt = 0;
        for(int i=0;i<h;i++){
            for(int j=0;j<l;j++){
                if(grid[i][j] == 1){
                    maxCnt++;
                    bfs(i,j,grid,dis,cnt);
                }
            }
        }
        for(int i=0;i<h;i++){
            for(int j=0;j<l;j++){
                if(cnt[i][j] == maxCnt){
                    min = Math.min(min,dis[i][j]);
                }
            }
        }
        if(min == Integer.MAX_VALUE) min = -1;
        return min;
    }
    int[][] dirs= {{1,0},{0,1},{-1,0},{0,-1}};
    private boolean in(int y,int x){
        return y<h && x<l && y>=0 && x>=0;
    }
    private void bfs(int y,int x,int[][] grid,int[][] dis,int[][] cnt){
        Queue<int[]> q = new LinkedList<>();
        int step = 1;
        q.offer(new int[]{y,x});
        boolean[][] vis = new boolean[h][l];
        vis[y][x] = true;
        while(!q.isEmpty()){
            int qsize = q.size();
            while(qsize>0){
                qsize--;
                int[] cur =q.poll();
                for(int[] dir : dirs){
                    int ny = cur[0]+dir[0];
                    int nx = cur[1]+dir[1];
                    if(in(ny,nx) && !vis[ny][nx] && grid[ny][nx] == 0){
                        vis[ny][nx] = true;
                        dis[ny][nx]+=step;
                        cnt[ny][nx]++;
                        q.offer(new int[]{ny,nx});
                    }
                }
            }
            step++;
        }
        
    }