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.
Have you met this question in a real interview? YesProblem Correction
Example
Example 1
Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
Explanation:
In this example, there are 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.
Example 2
Input: [[1,0],[0,0]]
Output: 1
In this example, there is one buildings at (0,0).
1 - 0
| |
0 - 0
The point (1,0) or (0,1) is an ideal empty land to build a house, as the total travel distance of 1 is minimal. So return 1.
public class Solution {
static class Pair {
int distSum = 0, buildings = 0;
}
public int shortestDistance(int[][] grid) {
int m = grid.length, n = grid[0].length;
int totalBuildings = 0;
Pair dist[][] = new Pair[m][n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
dist[i][j] = new Pair();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) {
BFS(grid, i, j, dist, m, n);
totalBuildings++;
}
int minDist = Integer.MAX_VALUE;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 0 && dist[i][j].buildings == totalBuildings)
minDist = Math.min(minDist, dist[i][j].distSum);
return minDist;
}
public void BFS(int[][] grid, int x, int y, Pair[][] dist, int m, int n) {
int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
Queue<int[]> q = new LinkedList<>();
boolean[][] visited = new boolean[m][n];
q.add(new int[] { x, y });
int count = 1;
while (q.size() != 0) {
int size = q.size();
while (size-- > 0) {
int[] node = q.poll();
for (int i = 0; i < 4; i++) {
int newX = node[0] + dir[i][0];
int newY = node[1] + dir[i][1];
if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[newX].length
&& grid[newX][newY] == 0 && !visited[newX][newY]) {
visited[newX][newY] = true;
dist[newX][newY].distSum += count;
dist[newX][newY].buildings++;
q.add(new int[] { newX, newY });
}
}
}
count++;
}
}
}