317. Shortest Distance from All Buildings

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)

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]++;
                    }
                }
            }
        }
    }
}