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
-1and 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