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 the idea of traversing the maze.

Need to use the 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, 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 The 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;
        }
    }
}

All Problems

All Solutions