317

317. Shortest Distance from All Buildings (Hard)

You are given an m x n grid grid of values 0, 1, or 2, where:

• each 0 marks an empty land that you can pass by freely,
• each 1 marks a building that you cannot pass through, and
• each 2 marks an obstacle that you cannot pass through.

You want to build a house on an empty land that reaches all buildings in the shortest total travel distance. You can only move up, down, left, and right.

Return the shortest travel distance for such a house. If it is not possible to build such a house according to the above rules, return -1.

The total travel distance is the sum of the distances between the houses of the friends and the meeting point.

The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

 

Example 1:

Input: grid = [[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.

Example 2:

Input: grid = [[1,0]]
Output: 1

Example 3:

Input: grid = [[1]]
Output: -1

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] is either 0, 1, or 2.
• There will be at least one building in the grid.

Companies:
Facebook, DoorDash, Google

Related Topics:
Array, Breadth-First Search, Matrix

Similar Questions:

• Walls and Gates (Medium)
• Best Meeting Point (Hard)
• As Far from Land as Possible (Medium)

Solution 1. BFS

// OJ: https://leetcode.com/problems/shortest-distance-from-all-buildings/
// Author: github.com/lzl124631x
// Time: O(LMN) where `L` is the number of ones
// Space: O(MN)
class Solution {
    int M, N;
    void updateDistance(vector<vector<int>> &A, int x, int y, vector<vector<int>> &B) {
        queue<pair<int, int>> q;
        q.emplace(x, y);
        vector<vector<bool>> seen(M, vector<bool>(N));
        int step = 0, dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}, cnt = 0;
        while (q.size()) {
            int cnt = q.size();
            ++step;
            while (cnt--) {
                auto [x, y] = q.front();
                q.pop();
                for (auto &[dx, dy] : dirs) {
                    int a = x + dx, b = y + dy;
                    if (a < 0 || b < 0 || a >= M || b >= N || A[a][b] != 0 || seen[a][b]) continue;
                    seen[a][b] = true;
                    q.emplace(a, b);
                    if (B[a][b] != INT_MAX) B[a][b] += step;
                }
            }
        }
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == 0 && !seen[i][j]) B[i][j] = INT_MAX;
            }
        }
    }
public:
    int shortestDistance(vector<vector<int>>& A) {
        M = A.size(), N = A[0].size();
        int ans = INT_MAX;
        vector<vector<int>> B(M, vector<int>(N)); // distance
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == 1) updateDistance(A, i, j, B);
            }
        }
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == 0) ans = min(ans, B[i][j]);
            }
        }
        return ans == INT_MAX ? -1 : ans;
    }
};