描述

給出一個二維的網(wǎng)格，每一格可以代表墻 2 ，房子 1，以及空 0 (用數(shù)字0,1,2來表示)，在網(wǎng)格中找到一個位置去建立郵局，使得所有的房子到郵局的距離和是最小的。
返回所有房子到郵局的最小距離和，如果沒有地方建立郵局，則返回-1.

注意事項

你不能穿過房子和墻，只能穿過空地。
你只能在空地建立郵局。
您在真實的面試中是否遇到過這個題？ Yes

樣例

給出一個網(wǎng)格：

    0 1 0 0 0
    1 0 0 2 1
    0 1 0 0 0

返回 8，你可以在(1,1)處建立郵局 (在(1,1)處建立郵局，所有房子到郵局的距離是最近的)。

挑戰(zhàn)

在O(n^3)內(nèi)的時間復(fù)雜度解決此問題。

代碼

class Coordinate {
    int x, y;
    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Solution {
    public int EMPTY = 0;
    public int HOUSE = 1;
    public int WALL = 2;
    public int[][] grid;
    public int n, m;
    public int[] deltaX = {0, 1, -1, 0};
    public int[] deltaY = {1, 0, 0, -1};
    
    // 得到網(wǎng)格中所有給定類型的位置坐標
    private List<Coordinate> getCoordinates(int type) {
        List<Coordinate> coordinates = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == type) {
                    coordinates.add(new Coordinate(i, j));
                }
            }
        }
        
        return coordinates;
    }
    
    // setGrid方法可以將二維網(wǎng)格的值傳遞給全局變量grid，m，n
    // 這樣不必每個方法都傳遞這三個形參
    private void setGrid(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        this.grid = grid;
    }
    
    private boolean inBound(Coordinate coor) {
        if (coor.x < 0 || coor.x >= n) {
            return false;
        }
        if (coor.y < 0 || coor.y >= m) {
            return false;
        }
        return grid[coor.x][coor.y] == EMPTY;
    }

    /**
     * @param grid a 2D grid
     * @return an integer
     */
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return -1;
        }
        
        // set n, m, grid
        setGrid(grid);
        
        List<Coordinate> houses = getCoordinates(HOUSE);
        
        // 初始化時distanceSum和visitedTimes直接被設(shè)為0；
        int[][] distanceSum = new int[n][m];
        int[][] visitedTimes = new int[n][m];;
        for (Coordinate house : houses) {
            bfs(house, distanceSum, visitedTimes);
        }
        
        int shortest = Integer.MAX_VALUE;
        List<Coordinate> empties = getCoordinates(EMPTY);
        for (Coordinate empty : empties) {
            // 若出現(xiàn)下列情況說明空點被房子阻礙了，不能到達所有房子的點不需要
            if (visitedTimes[empty.x][empty.y] != houses.size()) {
                continue;
            }
            
            shortest = Math.min(shortest, distanceSum[empty.x][empty.y]);
        }
        
        // 可能沒有一塊空地可以到達所有房子
        if (shortest == Integer.MAX_VALUE) {
            return -1;
        }
        return shortest;
    }
    
    /* bfs遍歷的是所有房子，bfs過程得到了每塊空地到所有它能到達的房子的距離總和
     * 以及每塊空地能被多少個房子訪問
     */
    private void bfs(Coordinate start,
                     int[][] distanceSum,
                     int[][] visitedTimes) {
        Queue<Coordinate> queue = new LinkedList<>();
        // hash用于去重
        boolean[][] hash = new boolean[n][m];
        
        queue.offer(start);
        hash[start.x][start.y] = true;
        /* bfs中必須要有對steps = 0 的初始化，因為每次bfs都要把steps重置為0，
         * 不然從另外的點開始bfs，step還是上次的，就會出bug
         */
        int steps = 0;
       
        while (!queue.isEmpty()) {
            // 分層遍歷，每算完隊列中的一層數(shù)steps更新一次
            steps++;
            int size = queue.size();
            // 如果不分層遍歷，隊列每poll一個坐標，steps就會更新一次，實際上應(yīng)該是將一層元素poll完后steps才更新
            // 在分層遍歷時，隊列要在層的for循環(huán)中poll坐標，不然就會出現(xiàn)重復(fù)size次遍歷當前poll的坐標的相鄰四個坐標，結(jié)果必然是錯誤的
            for (int temp = 0; temp < size; temp++) {
                Coordinate coor = queue.poll();
                for (int i = 0; i < 4; i++) {
                    Coordinate adj = new Coordinate(
                        coor.x + deltaX[i],
                        coor.y + deltaY[i]
                    );
                    if (!inBound(adj)) {
                        continue;
                    }
                    // 訪問過的點就不要再訪問了
                    if (hash[adj.x][adj.y]) {
                        continue;
                    }
                    queue.offer(adj);
                    hash[adj.x][adj.y] = true;
                    // 多個house到同一片空地的距離累加
                    distanceSum[adj.x][adj.y] += steps;
                    // 對每個house而言，每個空地只會訪問一次
                    // visitedTimes記錄的是每個空地被訪問的總次數(shù)
                    visitedTimes[adj.x][adj.y]++;
                    
                }
            }
        }
    }
}

出bug的一個地方：

代碼

bfs中的本該存在的steps = 0初始化寫到了20行的public int steps = 0位置;出現(xiàn)了bug，原因是steps表示空地到當前傳入house的位置的距離，在bfs中應(yīng)存在對steps = 0的初始化，每傳入一個house的位置，steps必須初始化為0；若將steps設(shè)為全局變量，則下一個house位置的steps是在上一個house的steps的基礎(chǔ)上計算的

輸出