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. For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

1 - 0 - 2 - 0 - 1 | | | | | 0 - 0 - 0 - 0 - 0 | | | | | 0 - 0 - 1 - 0 - 0 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.

Hint

Train of Thought

Short version: BFS from every building, calculate the distances and find the minimum distance in the end.

Key optimization : we do not go into a land, if it is not accessible by at least one of previous buildings.

I don't use a fresh "visited" for each BFS. Instead, I walk only onto the cells that were reachable from all previous buildings. From the first building I only walk onto cells where grid is 0, and make them -1. From the second building I only walk onto cells where grid is -1, and I make them -2. And so on.

For a long explanation see here in my blog.

It runs in 13 ms.

It is the same idea as stefan's c++ solution. I didn't see it until now. I did this myself.

Also one may want to make a copy of grid if it is not suppose to be modified.

Code

int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};

public int shortestDistance(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dist = new int[m][n];
    // Initialize building list and accessibility matrix `grid`
    List<Tuple> buildings = new ArrayList<>();
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 1)
                buildings.add(new Tuple(i, j, 0));
            grid[i][j] = -grid[i][j];
        }
    // BFS from every building, the kth building can only walks on grid[i][j] == k 
    for (int k = 0; k < buildings.size(); ++k)
        bfs(buildings.get(k), k, dist, grid, m, n);
    // Find the minimum distance
    int ans = -1;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (grid[i][j] == buildings.size() && (ans < 0 || dist[i][j] < ans))
                ans = dist[i][j];
    return ans;
}

public void bfs(Tuple root, int k, int[][] dist, int[][] grid, int m, int n) {
    Queue<Tuple> q = new ArrayDeque<>();
    q.add(root);
    while (!q.isEmpty()) {
        Tuple b = q.poll();
        dist[b.y][b.x] += b.dist;
        for (int i = 0; i < 4; ++i) {
            int x = b.x + dx[i], y = b.y + dy[i];
            if (y >= 0 && x >= 0 && y < m && x < n && grid[y][x] == k) {
                grid[y][x] = k + 1;
                q.add(new Tuple(y, x, b.dist + 1));
            }
        }
    }
}
class Tuple {
    public int y;
    public int x;
    public int dist;

    public Tuple(int y, int x, int dist) {
        this.y = y;
        this.x = x;
        this.dist = dist;
    }
}

Complexity