Question

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

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.

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

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(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Deque<int[]> q = new LinkedList<>();
        int total = 0;
        int[][] cnt = new int[m][n];
        int[][] dist = new int[m][n];
        int[] dirs = {-1, 0, 1, 0, -1};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    ++total;
                    q.offer(new int[] {i, j});
                    int d = 0;
                    boolean[][] vis = new boolean[m][n];
                    while (!q.isEmpty()) {
                        ++d;
                        for (int k = q.size(); k > 0; --k) {
                            int[] p = q.poll();
                            for (int l = 0; l < 4; ++l) {
                                int x = p[0] + dirs[l];
                                int y = p[1] + dirs[l + 1];
                                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0
                                    && !vis[x][y]) {
                                    ++cnt[x][y];
                                    dist[x][y] += d;
                                    q.offer(new int[] {x, y});
                                    vis[x][y] = true;
                                }
                            }
                        }
                    }
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0 && cnt[i][j] == total) {
                    ans = Math.min(ans, dist[i][j]);
                }
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

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;
    }
};

class Solution:
    def shortestDistance(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        q = deque()
        total = 0 # total building count
        # cnt: how many buildings can reach (x,y)
        #      if there is a column all blockers, then (x,y) cannot reach every building
        cnt = [[0] * n for _ in range(m)]
        dist = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    total += 1
                    q.append((i, j))
                    d = 0
                    vis = set() # reset for every free-land
                    while q:
                        d += 1
                        for _ in range(len(q)):
                            r, c = q.popleft()
                            for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                                x, y = r + a, c + b
                                if (
                                    0 <= x < m
                                    and 0 <= y < n
                                    and grid[x][y] == 0
                                    and (x, y) not in vis
                                ):
                                    cnt[x][y] += 1
                                    dist[x][y] += d
                                    q.append((x, y))
                                    vis.add((x, y))
        ans = inf
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0 and cnt[i][j] == total:
                    ans = min(ans, dist[i][j])
        return -1 if ans == inf else ans

############

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

func shortestDistance(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	var q [][]int
	total := 0
	cnt := make([][]int, m)
	dist := make([][]int, m)
	for i := range cnt {
		cnt[i] = make([]int, n)
		dist[i] = make([]int, n)
	}
	dirs := []int{-1, 0, 1, 0, -1}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				total++
				q = append(q, []int{i, j})
				vis := make([]bool, m*n)
				d := 0
				for len(q) > 0 {
					d++
					for k := len(q); k > 0; k-- {
						p := q[0]
						q = q[1:]
						for l := 0; l < 4; l++ {
							x, y := p[0]+dirs[l], p[1]+dirs[l+1]
							if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0 && !vis[x*n+y] {
								cnt[x][y]++
								dist[x][y] += d
								q = append(q, []int{x, y})
								vis[x*n+y] = true
							}
						}
					}
				}
			}
		}
	}

	ans := math.MaxInt32
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 0 && cnt[i][j] == total {
				if ans > dist[i][j] {
					ans = dist[i][j]
				}
			}
		}
	}
	if ans == math.MaxInt32 {
		return -1
	}
	return ans
}

317 - Shortest Distance from All Buildings

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions