1.Shortest Distance from All Buildings

題目描述

你想在空地上建造一座房子，以 最短距離到達所有建筑物。你只能向上，向下，向左和向右移動。您將得到值為0,1或2的二維網(wǎng)格，其中：

每個0標記一個空的土地，你可以自由穿過。
每個1標記一個你無法通過的建筑物。
每2個標記都是你無法通過的障礙。
例如，在給定的三棟樓 (0,0)， (0,4)， (2,2)以及障礙物在 (0,2)：

這個點 (1,2) 是建造房屋的理想空地，因為3 + 3 + 1 = 7的總行程距離是最小的。所以返回7。

注意：
將會有至少一個建筑物。如果根據(jù)上述規(guī)則無法建造這樣的房屋，則返回-1。

題目分析

這道題要求最短的距離，一般這種要求可以到的地方的距離，都需要把整個圖遍歷一遍，遍歷一般就是bfs和dfs。

這道題不用dfs的原因是：empty的位置到building的距離是按最小值來算的，用dfs每次如果放入depth不一定是最小的距離，每次都得更新，沒有效率。這道題用bfs的原因：一樣的原因，因為距離就是按照最小的距離來算的，完全是bfs的思路。

visited一般兩種方式：用一個boolean的矩陣，直接改寫grid的值。這里用第二種。-grid[i] [j]表示(i, j)點可以reach到的building數(shù)目。當grid[i][j] == # of buildings so far時，證明當前點還沒被visited，且當前點被之前所有的buildings都visited過，那么每次bfs只訪問這些點。如果該point沒有被之前所有的buildings訪問過，就不可能成為答案（根據(jù)要求empty的位置能到所有的buildings），其他與它相鄰的點也是這樣。和用boolean矩陣比，縮小了每次遍歷的范圍。

從每一個building，即grid[i] [j] == 1的點開始做bfs層次遍歷。

代碼實現(xiàn)

public class Solution {
    public int shortestDistance(int[][] grid) {
        int rows = grid.length;
        if (rows == 0) {
            return -1;
        }
        int cols = grid[0].length;
 
        // 記錄到各個building距離和
        int[][] dist = new int[rows][cols];
        
        // 記錄到能到達的building的數(shù)量
        int[][] nums = new int[rows][cols];            
        int buildingNum = 0;
        
        // 從每個building開始BFS
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {
                    buildingNum++;
                    bfs(grid, i, j, dist, nums);
                }
            }
        }
        
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 0 && dist[i][j] != 0 && nums[i][j] == buildingNum)
                    min = Math.min(min, dist[i][j]);
            }
        }
        if (min < Integer.MAX_VALUE)
            return min;
        return -1;
    }
    
    public void bfs(int[][] grid, int row, int col, int[][] dist, int[][] nums) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{row, col});
        int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        
        // 記錄訪問過的點
        boolean[][] visited = new boolean[rows][cols];
        int level = 0;
        while (!q.isEmpty()) {
            level++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] coords = q.remove();
                for (int k = 0; k < dirs.length; k++) {
                    int x = coords[0] + dirs[k][0];
                    int y = coords[1] + dirs[k][1];
                    if (x >= 0 && x < rows && y >= 0 && y < cols && !visited[x][y] && grid[x][y] == 0) {
                        visited[x][y] = true;
                        dist[x][y] += level;
                        nums[x][y]++;
                        q.add(new int[]{x, y});
                    }
                }
            }
        }
    }
}

參考文獻
[1] Shortest Distance from All Buildings