Leetcode317-Shortest-Distance-from-All-Buildings

Posted on In

题目描述

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. 
    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.

解析

题目要求找到一个点，使得其到所有building也就是标记为1的点的距离和最小，距离的定义是上下左右移动的距离，学名为Hamilton距离，这是一道非常典型的BFS题，对每个building依次进行BFS即可，不过需要注意的是，有的点只能到一些building到达不了全部building，我们在做BFS的时候，最后可以将visited和grid进行比较，如果发现有点是可以经过却没有visit则说明该点从这个building不可达，距离设为无穷大，剔除即可。

代码如下：

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
private int[] dx = {1,-1,0,0};
private int[] dy = {0,0,1,-1};
int n;
int m;
public int shortestDistance(int[][] grid) {
    if(grid.length == 0)
        return -1;
    int[][] dis = new int[grid.length][grid[0].length];
    n = grid.length;
    m = grid[0].length;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(grid[i][j] == 1){
                int[] start = {i, j};
                BFS(grid, dis, start);
            }
        }
    }
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(grid[i][j] == 0)
                min = Math.min(min, dis[i][j]);
        }
    }
    return min == Integer.MAX_VALUE ? -1 : min;
}

private void BFS(int[][] grid, int[][] dis, int[] start){
    Queue<int[]> q = new LinkedList<>();
    q.add(start);
    int[][] visited = new int[n][m];
    int dist = 0;
    int count = 1;
    visited[start[0]][start[1]] = 1;
    while(!q.isEmpty()){
    int nextcount = 0;
    for(int i = 0; i < count; i++){
        int x = q.peek()[0];
        int y = q.peek()[1];
        q.poll();
        dis[x][y] += dist;
        for(int j = 0; j < 4; j++){
            int newx = x + dx[j];
            int newy = y + dy[j];
            if(newx < 0 || newx >= n || newy < 0 || newy >= m)
                continue;
            if(visited[newx][newy] == 0 && grid[newx][newy] == 0 && dis[newx][newy] != Integer.MAX_VALUE){
                nextcount++;
                int[] point = {newx,newy};
                q.add(point);
                visited[newx][newy] = 1;
            }
        }
    }
        count = nextcount;
        dist++;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(visited[i][j] == 0 && grid[i][j] == 0)
                dis[i][j] = Integer.MAX_VALUE;
        }
    }
    
}

总结

总结下，这是一道Leetcode Hard，不过只要熟练掌握BFS就可以轻松搞定，本题就当给自己记录一份BFS的模板，属于公司面试、笔试高频题，我在Mathwork OA的时候就做到过此题的变种，需要熟练掌握，bug free