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):
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.Solutions:¶
public class Solution {
public int shortestDistance(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return -1;
}
Queue<Integer> xs = new LinkedList<Integer>();
Queue<Integer> ys = new LinkedList<Integer>();
int[][] sums = new int[grid.length][grid[0].length];
int[][] reach = new int[grid.length][grid[0].length];
for (int i = 0; i < grid.length; i ++) {
for (int j = 0; j < grid[0].length; j ++) {
if (grid[i][j] == 1) {
xs.add(i);
ys.add(j);
}
}
}
int target = xs.size();
int min = Integer.MAX_VALUE;
boolean found = false;
while (!xs.isEmpty()) {
boolean[][] visited = new boolean[grid.length][grid[0].length];
int x = xs.poll();
int y = ys.poll();
Queue<Integer> qx = new LinkedList<Integer>();
Queue<Integer> qy = new LinkedList<Integer>();
Queue<Integer> dis = new LinkedList<Integer>();
qx.add(x);
qy.add(y);
dis.add(0);
while (!qx.isEmpty()) {
int i = qx.poll();
int j = qy.poll();
int d = dis.poll();
if (i - 1 >= 0 && visited[i - 1][j] == false && grid[i - 1][j] == 0) {
qx.add(i - 1);
qy.add(j);
dis.add(d + 1);
visited[i - 1][j] = true;
}
if (i + 1 < grid.length && visited[i + 1][j] == false && grid[i + 1][j] == 0) {
qx.add(i + 1);
qy.add(j);
dis.add(d + 1);
visited[i + 1][j] = true;
}
if (j - 1 >= 0 && visited[i][j - 1] == false && grid[i][j - 1] == 0) {
qx.add(i);
qy.add(j - 1);
dis.add(d + 1);
visited[i][j - 1] = true;
}
if (j + 1 < grid[0].length && visited[i][j + 1] == false && grid[i][j + 1] == 0) {
qx.add(i);
qy.add(j + 1);
dis.add(d + 1);
visited[i][j + 1] = true;
}
if (d != 0) {
sums[i][j] += d;
reach[i][j] ++;
if (xs.isEmpty() && reach[i][j] == target) {
found = true;
min = Math.min(min, sums[i][j]);
}
}
}
}
if (found == false) {
return -1;
}
return min;
}
}
public class Solution {
public int shortestDistance(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return -1;
}
int result = Integer.MAX_VALUE, look = 0;
int[][] sums = new int[grid.length][grid[0].length];
int[][] dirs = new int[][]{{0,-1},{-1,0},{0,1},{1,0}};
for (int i = 0; i < grid.length; i ++) {
for (int j = 0; j < grid[0].length; j ++) {
if (grid[i][j] == 1) {
result = Integer.MAX_VALUE;
Queue<Integer> xs = new LinkedList<Integer>();
Queue<Integer> ys = new LinkedList<Integer>();
Queue<Integer> dis = new LinkedList<Integer>();
xs.add(i);
ys.add(j);
dis.add(0);
while (!xs.isEmpty()) {
int x = xs.poll();
int y = ys.poll();
int d = dis.poll();
for (int k = 0; k < dirs.length; k ++) {
int nX = x + dirs[k][0];
int nY = y + dirs[k][1];
if (nX >= 0 && nX < grid.length && nY >= 0 && nY < grid[0].length && grid[nX][nY] == look) {
grid[nX][nY] --;
sums[nX][nY] += d + 1;
xs.add(nX);
ys.add(nY);
dis.add(d + 1);
result = Math.min(result, sums[nX][nY]);
}
}
}
look --;
}
}
}
return result == Integer.MAX_VALUE ? -1 : result;
}
}