广度优先遍历的单独应用（Java）

1.Shortest Distance from All Buildings

题目描述

你想在空地上建造一座房子，以最短距离到达所有建筑物。你只能向上，向下，向左和向右移动。您将得到值为0,1或2的二维网格，其中：

每个0标记一个空的土地，你可以自由穿过。
每个1标记一个你无法通过的建筑物。
每2个标记都是你无法通过的障碍。
例如，在给定的三栋楼 (0,0)， (0,4)， (2,2)以及障碍物在 (0,2)：

这个点 (1,2) 是建造房屋的理想空地，因为3 + 3 + 1 = 7的总行程距离是最小的。所以返回7。

注意：
将会有至少一个建筑物。如果根据上述规则无法建造这样的房屋，则返回-1。

题目分析

这道题要求最短的距离，一般这种要求可以到的地方的距离，都需要把整个图遍历一遍，遍历一般就是bfs和dfs。

这道题不用dfs的原因是：empty的位置到building的距离是按最小值来算的，用dfs每次如果放入depth不一定是最小的距离，每次都得更新，没有效率。这道题用bfs的原因：一样的原因，因为距离就是按照最小的距离来算的，完全是bfs的思路。

visited一般两种方式：用一个boolean的矩阵，直接改写grid的值。这里用第二种。-grid[i] [j]表示(i, j)点可以reach到的building数目。当grid[i][j] == # of buildings so far时，证明当前点还没被visited，且当前点被之前所有的buildings都visited过，那么每次bfs只访问这些点。如果该point没有被之前所有的buildings访问过，就不可能成为答案（根据要求empty的位置能到所有的buildings），其他与它相邻的点也是这样。和用boolean矩阵比，缩小了每次遍历的范围。

从每一个building，即grid[i] [j] == 1的点开始做bfs层次遍历。

代码实现

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的数量
        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

最后编辑于：2018.04.06 08:16:45