Leetcode(317) Shortest Distance from All Buildings

发表于 | 分类于

Description

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解题，cnt数组存储能达到的building数目，dis记录到各building的距离合。就是麻烦了一点，没办法，没法用DFS写，因为没法保证最小距离

具体代码如下：

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
67
68
69
70
71
72
73
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    /**
     * @param grid: the 2D grid
     * @return: the shortest distance
     */
    static public int shortestDistance(int[][] grid) {
        int result = Integer.MAX_VALUE;
        int[][] dis = new int[grid.length][grid[0].length];
        int[][] cnt = new int[grid.length][grid[0].length];
        int buildingcnt = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] != 1) {
                    continue;
                }
                buildingcnt++;
                int x = i;
                int y = j;
                int[][] visit = new int[grid.length][grid[0].length];
                int[] dirx = {0, 0, 1, -1};
                int[] diry = {1, -1, 0, 0};
                visit[x][y] = 1;
                Node newpair = new Node(x, y);
                Queue<Node> q = new LinkedList<>();
                q.add(newpair);
                int step = 0;
                dis[x][y] = step;
                while (!q.isEmpty()) {
                    int size = q.size();
                    for (int s = 0; s < size; s++) {
                        Node p = q.poll();
                        x = p.x;
                        y = p.y;
                        dis[x][y] += step;
                        cnt[x][y] += 1;
                        for (int ii = 0; ii < 4; ii++) {
                            int nexti = x + dirx[ii];
                            int nextj = y + diry[ii];
                            if (nexti >= 0 && nexti < grid.length && nextj >= 0 && nextj < grid[0].length && visit[nexti][nextj] == 0 && grid[nexti][nextj] == 0) {
                                q.add(new Node(nexti, nextj));
                                visit[nexti][nextj] = 1;
                            }
                        }
                    }
                    step += 1;
                }
            }
        }
        for (int i = 0; i < dis.length; i++) {
            for (int j = 0; j < dis[0].length; j++) {
                result = dis[i][j] < result && grid[i][j] == 0 && cnt[i][j] == buildingcnt ? dis[i][j] : result;
            }
        }
        if (result == Integer.MAX_VALUE) {
            return -1;
        }
        return result;
    }

}

class Node {
    int x;
    int y;

    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}