GuilinDev

Lc0317

05 August 2008

317 Shortest Distance from All Buildings

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

  • Each 0 marks an empty land which you can pass by freely.
  • Each 1 marks a building which you cannot pass through.
  • Each 2 marks an obstacle which you cannot pass through.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13

Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

Output: 7 

Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2),
             the point (1,2) is an ideal empty land to build a house, as the total 
             travel distance of 3+3+1=7 is minimal. So return 7.

Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

分析

BFS

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

class Solution {

    private int[][] dirs = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };

    // 思路：
    //  (1) 从每一个建筑物开始进行广度优先搜索
    //  (2) 在搜索的同时计算每一个空格到这个建筑物的距离
    //  (3) 在搜索的同时将每一个空格到每一个建筑物的距离进行累加，得到每个空格到所有建筑物的距离
    //  (4) 取空格到所有建筑物的最小距离
    public int shortestDistance(int[][] grid) {
        int rows = grid.length;
        if (rows == 0) {
            return 0;
        }
        int cols = grid[0].length;

        int[][] totalDist = new int[rows][cols];
        int result = Integer.MAX_VALUE;
        // 用于标记空地
        int mark = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // (1) 从每一个建筑物开始进行广度优先搜索
                if (grid[i][j] == 1) {
                    result = bfs(grid, rows, cols, i, j, mark, totalDist);
                    // 每次遍历搜索完一个建筑物，这个标记减一，表示所有空地被遍历一次了
                    mark--;
                }
            }
        }

        return result;
    }

    private int bfs(int[][] grid, int m, int n, int i, int j, int mark, int[][] totalDist) {
        int result = Integer.MAX_VALUE;
        Queue<int[]> queue = new LinkedList<>();
        // 队列中每个数组有 3 个元素，分别表示：
        // 第一个元素和第二个元素表示坐标值
        // 第三个元素表示当前坐标到建筑物的距离
        // 第三个元素的初始值为 0 的原因是：一开始的时候从当前建筑物到当前建筑物的距离是 0
        queue.add(new int[]{i, j, 0});
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int currDist = curr[2];
            for (int[] dir : dirs) {
                int row = curr[0] + dir[0];
                int col = curr[1] + dir[1];
                if (row >= 0 && row < m && col >= 0 && col < n && grid[row][col] == mark) {
                    // (2) 在搜索的同时计算每一个空格到这个建筑物的距离
                    int dist = currDist + 1;
                    // (3) 在搜索的同时将每一个空格到每一个建筑物的距离进行累加
                    totalDist[row][col] += dist;
                    // (4) 取空格到所有建筑物的最小距离
                    result = Math.min(result, totalDist[row][col]);

                    queue.add(new int[]{row, col, dist});
                    // 和 mark 标识对应
                    grid[row][col]--;
                }
            }
        }
        return result == Integer.MAX_VALUE ? -1 : result;
    }
}
This site is open source. Improve this page.