This page explains Java solution to problem Shortest Distance from All Buildings
using Breadth First Search
algorithm.
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:
Input:
[
[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.
package com.vc.hard;
import java.util.*;
class ShortestDistanceFromAllBuildings {
public int shortestDistance(int[][] grid) {
if(grid == null || grid.length == 0) return 0;
int m = grid.length;
int n = grid[0].length;
int[][] total = new int[m][n];
int[][] count = new int[m][n];
int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int totalBuilding = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == 1) {
totalBuilding++;
Queue<int[]> q = new LinkedList<>();
boolean[][] visited = new boolean[m][n];
q.offer(new int[]{i, j});
int level = 0;
while(!q.isEmpty()) {
int size = q.size();
for(int e = 0; e < size; e++) {
int[] point = q.poll();
int x = point[0];
int y = point[1];
if(visited[x][y] || grid[x][y] == 2) continue;
visited[x][y] = true;
for(int[] dir: dirs) {
int xNew = x + dir[0];
int yNew = y + dir[1];
if(xNew >= 0 && xNew < grid.length && yNew >= 0 && yNew < grid[0].length
&& grid[xNew][yNew] != 1 && grid[xNew][yNew] != 2) {
q.offer(new int[]{xNew, yNew});
}
}
if(grid[x][y] == 0) {
total[x][y] += level;
count[x][y]++;
}
}
level++;
}
}
}
}
int res = Integer.MAX_VALUE;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(count[i][j] == totalBuilding) res = Math.min(res, total[i][j]);
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}
}
O((M * N)2)
M is total number of rows in an input array
N is total number of cols in an input array
O(M * N) Where
M is total number of rows in an input array
N is total number of cols in an input array