Problem: 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.
- It was given that there will be at least one building.
Example:
Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]] 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.
Approach: Basically if you see it is kind of getting the minimum distance in a unweighted graph. That means we can use BFS here. Basically we can apply BFS from every empty (0) point and calculate the distances to each building. We can then sum all distances and set it as current_distance if all the buildings are reachable from the start point.
We can then compare current_distance to min_distance and if min_distance is greater than current_distance then we can update the min_distance.
For optimization whenever we find that all the buildings are not reachable from a particular point then we can mark all the visited points during the BFS as obstacles (2) as there is no point in traversing through these points.
Implementation in C#:
public int ShortestDistance(int[][] grid)
{
int rows = grid.Length;
int cols = grid[0].Length;
int buildingCount = 0;
for (int i = 0; i < rows; ++i)
{
for (int j = 0; j < cols; ++j)
{
if (grid[i][j] == 1)
{
++buildingCount;
}
}
}
int minDistance = int.MaxValue;
for (int i = 0; i < rows; ++i)
{
for (int j = 0; j < cols; ++j)
{
if (grid[i][j] == 0)
{
int currDistance = this.CalculateDistance(grid, i, j, buildingCount);
if (currDistance != -1 && minDistance > currDistance)
{
minDistance = currDistance;
}
}
}
}
return minDistance == int.MaxValue ? -1 : minDistance;
}
private int CalculateDistance(int[][] grid, int startRow, int startCol, int buildingCount)
{
int totalDistance = 0;
Queue<int[]> queue = new Queue<int[]>();
queue.Enqueue(new int[] { startRow, startCol });
int rows = grid.Length;
int cols = grid[0].Length;
bool[,] visited = new bool[rows, cols];
visited[startRow, startCol] = true;
int visitedBuildingsCount = 0;
int currDistance = 0;
while (queue.Count > 0)
{
int size = queue.Count;
for (int i = 0; i < size; ++i)
{
int[] currCord = queue.Dequeue();
if (this.IsBuildingCoordinate(currCord, grid))
{
++visitedBuildingsCount;
totalDistance += currDistance;
if (visitedBuildingsCount == buildingCount)
{
return totalDistance;
}
}
else
{
this.AddNeighborsToQueue(currCord, queue, grid, visited);
}
}
++currDistance;
}
// All buildings are not reachable, for optimization mark all the visited nodes as obstacles
this.MarkInvalidPointsAsObstacle(grid, visited);
return -1;
}
private void MarkInvalidPointsAsObstacle(int[][] grid, bool[,] visited)
{
for (int i = 0; i < grid.Length; ++i)
{
for (int j = 0; j < grid[0].Length; ++j)
{
if (visited[i, j] && grid[i][j] != 1)
{
grid[i][j] = 2;
}
}
}
}
private void AddNeighborsToQueue(int[] currCord, Queue<int[]> queue, int[][] grid, bool[,] visited)
{
List<int[]> neighbors = new List<int[]>
{
new int[] { currCord[0] - 1, currCord[1] }, // up cordinate
new int[] { currCord[0] + 1, currCord[1] }, // down cordinate
new int[] { currCord[0], currCord[1] - 1 }, // left cordinate
new int[] { currCord[0], currCord[1] + 1 } //right cordinate
};
foreach (int[] neighbor in neighbors)
{
if (IsValidAndUnVisitedCordinate(neighbor, grid, visited))
{
visited[neighbor[0], neighbor[1]] = true;
queue.Enqueue(neighbor);
}
}
}
private bool IsValidAndUnVisitedCordinate(int[] cordinate, int[][] grid, bool[,] visited)
{
if (cordinate[0] < 0
|| cordinate[0] >= grid.Length
|| cordinate[1] < 0
|| cordinate[1] >= grid[0].Length
|| visited[cordinate[0], cordinate[1]]
|| grid[cordinate[0]][cordinate[1]] == 2)
{
return false;
}
return true;
}
private bool IsBuildingCoordinate(int[] currCord, int[][] grid)
{
return grid[currCord[0]][currCord[1]] == 1;
}
Complexity: O(m^2 * n ^ 2) where m is number of rows and n is number of columns
No comments:
Post a Comment