Here is the link.
First practice - C# - BFS - Queue - Case studies - Easy to follow
Nov. 30, 2020
It is a hard level algorithm. I chose to write the solution using BFS algorithm.
Case study
Sometimes there is no solution.
For example,
case 1:
1 , 1, 0
1, 0, 0
There is no way to access the building (0,0) position building. Return should be -1. So it is important to record how many buildings in total first, and then record how many buildings are accessible starting from the position with value 0. Compare two numbers, if any building is not accessible, return -1.
case 2:
How to set visited in the matrix, and make sure to avoid revisit the same position?
1 0 1
0 0 1
0 0 1
Space complexity should not be big concern. I prefer to use a copy of given matrix grid to pass into function to run BFS, and the value will be changed to mark visited.
Two concerns in my design, first is to do not count the same building more than once. The tip is to change the building value 1 to -1, so it can not be counted more than once.
Secondly it is ok to change value 0 to -1 as a way to mark visited land, same value as visited building. No worry about sharing the same value.
Let me walk through one search and see if it can be optimized.
Start from (0, 1) position since the value is 0, and then calculate the smallest distance to any building if it is accessible using BFS. BFS is very powerful tool to ensure the smallest distance is found first and it can be recorded properly.
Add integer array {0, 1, 0} to the queue, and then start BFS search; Dequeue {0, 1, 1}, the position in the matrix is (0,1), and the distance is 0. Check the position is building or not. If it is, then mark visit the building, add distance to total distance, return since it is not allowed to cross the building. If it is land, then add four possible neighbors into Queue, increment distance with value 1.
It is important to walk through the steps by hand, so it is easy to spot issues in the design.
Second step is to add four neighbors of (0, 1) to the queue, third step is to dequeue one by one those four positions.
Left neighbor is with value 1, one building is found, distance+=steps, and mark (0,0) with value -1.
Right neighbor is with value 1, another building is found, distance+=steps, and mark (0, 2) with value -1.
Down neighbor is with value 0, continue to search it's found neighbors.
Up neighbor is out-of-range.
Skip more details afterwards.
I do not think that it is needed to prune the algorithm if all buildings are found. Just let BFS search all possible paths and naturally end.
How to have a smoothly practice?
I have to work on my attention not to mix variables under stress, one tip is to reuse same variable, this way is to avoid mixing variables.
I wrote DFS first, and then I noticed that it did not work. It took me less than a few minutes to change them using Queue. But I do think that I have to pay more attention before I write the code. Think more carefully.
Additional checkings include the following:
- All buildings are found starting any position with 0 value in the given matrix;
- Distance is updated if one building is found;
- Make matrix a copy to pass as a function argument, easy to mark visit using -1, avoid duplicate count of same building;
- Avoid index-out-of-range error, do not declare valid checking variable after out-of-range check. Since only if it is in the range, then it is safe to check valid value; Put all checkings in one giant statement.
- I mixed row and col with x and y in my outOfRangeEtc, better to reuse row and col.
public class Solution {
public int ShortestDistance(int[][] grid) {
if(grid == null || grid.Length == 0 || grid[0].Length == 0)
return 0;
var rows = grid.Length;
var columns = grid[0].Length;
var buildingCount = 0;
for(int row = 0; row < rows; row++)
{
for(int col = 0; col < columns; col++)
{
if(grid[row][col] == 1)
{
buildingCount++;
}
}
}
// make sure buidling found == buildingCount
// distance - BFS - minimum
var minDistance = Int32.MaxValue;
for(int row = 0; row < rows; row++)
{
for(int col = 0; col < columns; col++)
{
var current = grid[row][col];
if(current != 0)
continue;
var found = 0;
var distance = 0;
var gridCopy = new int[rows][];
for(int row1 = 0; row1 < rows; row1++)
{
gridCopy[row1] = new int[columns];
}
for(int row1 = 0; row1 < rows; row1++)
{
for(int col1 = 0; col1 < columns; col1++)
{
gridCopy[row1][col1] = grid[row1][col1];
}
}
runBFS(gridCopy, row, col, ref found, ref distance);
if(found == buildingCount)
{
minDistance = Math.Min(minDistance, distance);
}
}
}
return minDistance == Int32.MaxValue? -1: minDistance;
}
private void runBFS(int[][] grid, int row, int col, ref int found, ref int distance)
{
var rows = grid.Length;
var columns = grid[0].Length;
var queue = new Queue<int[]>();
queue.Enqueue(new int[]{row, col, 0});
while (queue.Count > 0)
{
var count = queue.Count;
for (int i = 0; i < count; i++)
{
var node = queue.Dequeue();
var x = node[0];
var y = node[1];
var steps = node[2];
var outOfRangeEtc = x < 0 || x >= rows || y < 0 || y >= columns ||
grid[x][y] == 2 || grid[x][y] == -1;
if (outOfRangeEtc)
{
continue;
}
if (grid[x][y] == 1)
{
grid[x][y] = -1;
distance += steps;
found++;
}
else
{ // mark visit
grid[x][y] = -1;
queue.Enqueue(new int[] { x, y - 1, steps + 1 });
queue.Enqueue(new int[] { x, y + 1, steps + 1 });
queue.Enqueue(new int[] { x - 1, y, steps + 1 });
queue.Enqueue(new int[] { x + 1, y, steps + 1 });
}
}
}
}
}
