Question

Formatted question description: https://leetcode.ca/all/317.html

 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.

 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.

@not-real-similar: 296	Best Meeting Point
@similar: 286	Walls and Gates

Algorithm

In some cases, the obstacle completely blocks a certain building, then -1 should be returned. So this problem can only be solved by traversing the maze.

Need to use queue to traverse, we perform a BFS traversal of the whole picture for each building position, and establish a distance field of dist each time.

Since our BFS traversal needs to mark the locations that should be visited, and we don’t want to build a two-dimensional matrix of visits, then, what should we do, here is a small trick,

  • When we first traverse, we always find the position of 0. After the traversal, we assign it to -1.
  • In this way, in the next round of traversal, we will find the position of -1 and assign them all to -2,
  • And so on until all buildings are traversed

Then update the values of dist and sum during the traversal process. Note that our dist is a local variable, and it is initialized to grid every time. The real distance field is accumulated in sum. Since the position of the building is 1 in the grid, dist initialization in the middle is also 1, and it needs to be subtracted by 1 when added to the sum.

We use the value in the sum to update the value of the result res, and finally see if we want to return -1 according to the value of result.

Code

Java

  • import java.util.LinkedList;
    import java.util.Queue;
    
    public class Shortest_Distance_from_All_Buildings {
    
        public static void main(String[] args) {
            Shortest_Distance_from_All_Buildings out = new Shortest_Distance_from_All_Buildings();
            Solution s = out.new Solution();
    
            System.out.println(s.shortestDistance(new int[][] { {1,0,2,0,1},{0,0,0,0,0},{0,0,1,0,0} } ));
        }
    
        public class Solution {
            /**
             * @param grid: the 2D grid
             * @return: the shortest distance
             */
            public int shortestDistance(int[][] grid) {
                if (grid == null || grid.length == 0 || grid[0].length == 0) {
                    return 0;
                }
    
                int m = grid.length, n = grid[0].length;
                int[][] totalDistance = new int[m][n];
                int step = 0;
                int res = 0;
    
                for (int i = 0; i < m; ++i) {
                    for (int j = 0; j < n; ++j) {
                        if (grid[i][j] == 1) {
                            res = bfs(grid, i, j, step, totalDistance);
                            step--;
                        }
                    }
                }
    
                return res == Integer.MAX_VALUE ? -1 : res;
            }
    
            private int bfs(int[][] grid, int x, int y, int step, int[][] totalDistance) {
                int res = Integer.MAX_VALUE;
                int m = grid.length;
                int n = grid[0].length;;
    
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(x * n + y);
    
                int curDistance = 0;
                int[] directions = {-1, 0, 1, 0, -1};
    
                while (!queue.isEmpty()) {
                    int l = queue.size();
                    curDistance++;
                    while (l-- != 0) {
                        int t = queue.poll();
                        x = t / n; // restore. could also be a tuple(x,y) put in queue
                        y = t % n;
    
                        for (int i = 0; i < 4; ++i) {
                            int _x = x + directions[i], _y = y + directions[i + 1];
                            if (_x >= 0 && _x < m && _y >= 0 && _y < n && grid[_x][_y] == step) {
                                queue.offer(_x * n + _y);
                                totalDistance[_x][_y] += curDistance;
                                grid[_x][_y]--;
                                res = Math.min(res, totalDistance[_x][_y]);
                            }
                        }
                    }
                }
                return res;
            }
        }
    }
    
  • class Solution {
    public:
        int shortestDistance(vector<vector<int>>& grid) {
            int res = INT_MAX, buildingCnt = 0, m = grid.size(), n = grid[0].size();
            vector<vector<int>> dist(m, vector<int>(n, 0)), cnt = dist;
            vector<vector<int>> dirs{ {0,-1},{-1,0},{0,1},{1,0} };
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == 1) {
                        ++buildingCnt;
                        queue<pair<int, int>> q;
                        q.push({i, j});
                        vector<vector<bool>> visited(m, vector<bool>(n, false));
                        int level = 1;
                        while (!q.empty()) {
                            int size = q.size();
                            for (int s = 0; s < size; ++s) {
                                int a = q.front().first, b = q.front().second; q.pop();
                                for (int k = 0; k < dirs.size(); ++k) {
                                    int x = a + dirs[k][0], y = b + dirs[k][1];
                                    if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0 && !visited[x][y]) {
                                        dist[x][y] += level;
                                        ++cnt[x][y];
                                        visited[x][y] = true;
                                        q.push({x, y});
                                    }
                                }
                            }
                            ++level;
                        }
                    }
                }
            }
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == 0 && cnt[i][j] == buildingCnt) {
                        res = min(res, dist[i][j]);
                    }
                }
            }
            return res == INT_MAX ? -1 : res;
        }
    };
    
  • from collections import deque
    
    
    class Solution(object):
      def shortestDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
    
        def bfs(si, sj, grid, buildNum, hit):
          dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
          queue = deque([(si, sj, 0)])
          visited = set([(si, sj)])
          count = 1
          while queue:
            i, j, dist = queue.popleft()
            for di, dj in dirs:
              newi, newj = i + di, j + dj
              if (newi, newj) in visited:
                continue
              if 0 <= newi < len(grid) and 0 <= newj < len(grid[0]) and grid[newi][newj] != 2:
                if grid[newi][newj] != 1:
                  grid[newi][newj] -= dist + 1
                  hit[newi][newj] += 1
                  visited |= {(newi, newj)}
                  queue.append((newi, newj, dist + 1))
                else:
                  count += 1
                visited |= {(newi, newj)}
    
          if count != buildNum:
            print
            count, buildNum
            return False
          return True
    
        count = 0
        for i in range(0, len(grid)):
          for j in range(0, len(grid[0])):
            if grid[i][j] == 1:
              count += 1
    
        hit = [[0] * len(grid[0]) for _ in range(0, len(grid))]
        for i in range(0, len(grid)):
          for j in range(0, len(grid[0])):
            if grid[i][j] == 1:
              if not bfs(i, j, grid, count, hit):
                return -1
    
        ans = float("-inf")
        for i in range(0, len(grid)):
          for j in range(0, len(grid[0])):
            if grid[i][j] < 0 and hit[i][j] == count:
              ans = max(ans, grid[i][j])
              grid[i][j] = 0
        return -ans if ans != float("-inf") else -1
    
    

All Problems

All Solutions