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:

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),
             t
he 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.

Solution

(1) Java

class Solution {
    class Pair {
        int nbuilding = 0;
        int dist = 0;

        public Pair(int nb, int dist) {
            nbuilding = nb;
            this.dist = dist;
        }
    }

    public int shortestDistance(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int nbuilding = 0;
        int m = grid.length;
        int n = grid[0].length;
        int rst = Integer.MAX_VALUE;
        List<Pair> list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    nbuilding++;
                } else if (grid[i][j] == 0) {
                    Pair pair = traverse(grid, i, j);
                    list.add(pair);
                }
            }
        }
        for (Pair pair : list) {
            if (pair.nbuilding == nbuilding) {
                rst = Math.min(rst, pair.dist);
            }
        }
        return rst == Integer.MAX_VALUE ? -1 : rst;
    }

    private Pair traverse(int[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] visited = new int[m][n];
        visited[i][j] = 1;
        Deque<Integer> q = new LinkedList<>();
        q.offer(i*n+j);
        int dist = 0;
        int layer = 0;
        int buildingcount = 0;
        while(q.size() > 0) {
            int size = q.size();
            layer++;
            for (int k = 0; k < size; k++) {
                int pos = q.poll();
                int x = pos/n;
                int y = pos%n;
                if (x-1 >= 0 && visited[x-1][y] == 0 &&  grid[x-1][y] == 1) {
                    buildingcount++;
                    dist += layer;
                    visited[x-1][y] = 1;
                } else if (x-1 >= 0 && visited[x-1][y] == 0 &&  grid[x-1][y] == 0) {
                    q.offer((x-1)*n+y);
                    visited[x-1][y] = 1;
                } 
                if (x+1 < m && visited[x+1][y] == 0 &&  grid[x+1][y] == 1) {
                    buildingcount++;
                    dist += layer;
                    visited[x+1][y] = 1;
                } else if (x+1 < m && visited[x+1][y] == 0 &&  grid[x+1][y] == 0) {
                    q.offer((x+1)*n+y);
                    visited[x+1][y] = 1;
                } 
                if (y-1 >= 0 && visited[x][y-1] == 0 &&  grid[x][y-1] == 1) {
                    buildingcount++;
                    dist += layer;
                    visited[x][y-1] = 1;
                } else if (y-1 >= 0 && visited[x][y-1] == 0 &&  grid[x][y-1] == 0) {
                    q.offer(x*n+y-1);
                    visited[x][y-1]  = 1;
                } 
                if (y+1 < n && visited[x][y+1] == 0 &&  grid[x][y+1] == 1) {
                    buildingcount++;
                    dist += layer;
                    visited[x][y+1] = 1;
                } else if (y+1 < n && visited[x][y+1] == 0 &&  grid[x][y+1] == 0) {
                    q.offer(x*n+y+1);
                    visited[x][y+1] = 1;
                } 
            }
        }
        return new Pair(buildingcount, dist);
    }
}

(2) Python

(3) Scala