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:

1. Each 0 marks an empty land which you can pass by freely.
2. Each 1 marks a building which you cannot pass through.
3. 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.

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

Tips:

BFS，先找出所有building，然后算他们到每个building的距离存入dist数组，最后得出最近的点。有个trick就是用原数组grid来记录这个点能到几个building，能到一个building就+1。bfs中传入k代表遍历之前一个building时没有去过的点不用去了，相当于visited数组。

Code:

public class Solution {
    class Tuple {
        public int x;
        public int y;
        public int dist;

        public Tuple(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
    int[][] dir = new int[][] {{1, 0},{-1, 0},{0, 1},{0, -1}};
    public int shortestDistance(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n];
        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];
            }
        }
        for (int k = 0; k < buildings.size(); k++) {
            bfs(buildings.get(k), k, dist, grid, m, n);
        }
        int res = -1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == buildings.size() && (res < 0 || dist[i][j] < res)) res = dist[i][j];
            }
        }
        return res;
    }
    private void bfs(Tuple root, int k, int[][] dist, int[][] grid, int m, int n) {
        Queue<Tuple> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Tuple b = queue.poll();
            dist[b.x][b.y] += b.dist;
            for (int[] d : dir) {
                int x = b.x + d[0], y = b.y + d[1];
                if (x >= 0 && y >= 0 && x < m && y < n && grid[x][y] == k) {
                    grid[x][y] = k + 1;
                    queue.add(new Tuple(x, y, b.dist + 1));
                } 
            }
        }
    }
}