Here is the link.
Second practice - C# - no cost direction first - case study
Nov. 24, 2020
It is more efficient to handle no cost direction first using BFS, so I like to practice using C# LinkedList instead of Queue to handle the neighbor nodes.
Case study
grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
How to solve the problem ?
Record minimum cost for each position in the matrix.
Using C# double linked list LinkedList, a deque data structure.
cost[0][0] = 0,
Apply BFS algorithm, start from (0,0), go right to (0, 1) or go down to (1, 0).
grid[0][0] = 1 which is to go right, so cost[0][1] = 0, no need to change the direction.
But cost[1][0] = 1 since direction should go down.
So add (0, 1) to the head of linked list, and add (1, 0) to the end of double linked list.
so the cost matrix
0, 0, ?, ?
1, ?, ?, ?
?, ?, ?, ?
?, ?, ?, ?
Next step is to visit linked list and continue to apply BFS algorithm. Work on the head of linked list first, which is (0, 1).
Check (0, 1), there are three directions, go left or right or down. Go right, no cost. Go left, cost 1, but cost(0,0) = 0, new path is bigger than 0. Ignore.
Cost matrix is the following:
0, 0, 0, ?
1, 1, ?, ?
?, ?, ?, ?
So cost matrix will be the following:
0, 0, 0, 0
1, 1, 1, 1
?, ?, ?, ?,
?, ?, ?, ?
The linked list has four nodes in the order of {[1, 0],[1, 1],[1, 2],[1, 3]}.
I think that the above steps are good enough to figure out how to find minimum cost from top left to bottom right. The next step is to work on coding. One thing is to talk about time complexity.
Double linked list
Instead of using Queue, I choose to use C# LinkedList, all neighbor nodes with no cost will be added to front of linked list, nodes with cost will be added to the end of linked list.
C# LinkedList.AddFirst for no cost direction
C# LinkedList.AddLast for cost direction
To remove a node from the linked list, remove from the head of linked list. To understand design of C# LinkedList, a C# LinkedListNode is returned from LinkedList.RemoveFirst API call.
It is important for me to remember all those LinkedListNode APIs:
Properties
List
Next
Previous
Value
ValueRef
Questions to ask
Common mistakes and questions asked:
- What is most important in this problem solving? All possible paths should be examined so that minimum cost will be calculated correctly from top left corner to bottom right.
- How to ensure that all paths will be examined? What to keep in the search?
- Why do min cost of each position (row, col) in matrix should be calculated in order to get the bottom-right one?
- Why does the solution using two loops, one is to iterate each row, one is to iterate each column, it is not working? Is it a common mistake from interviewees?
public class Solution {
/// <summary>
/// Nov. 24, 2020
/// BFS approach
/// Work on BFS approach - work on no cost direction first, and then directions with cost next
/// Using C# LinkedList instead of Queue, deque - two ends.
/// </summary>
/// <param name="grid"></param>
/// <returns></returns>
public int MinCost(int[][] grid)
{
var rows = grid.Length;
var columns = grid[0].Length;
var cost = new int[rows][];
for (int row = 0; row < rows; row++)
{
cost[row] = new int[columns];
}
for (int row = 0; row < rows; row++)
{
for (int col = 0; col < columns; col++)
{
cost[row][col] = int.MaxValue;
}
}
cost[0][0] = 0;
var list = new LinkedList<int[]>();
list.AddLast(new int[] { 0, 0 });
// right, left, down, up
var directions = new int[,] { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
// 1 -> right, 2 <- left, 3 down, 4 up
while (list.Count > 0)
{
var node = list.First;
list.RemoveFirst();
// C# LinkedListNode - Value - get, set, Next, Previous
// https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.linkedlistnode-1.value?view=net-5.0
var row = node.Value[0];
var col = node.Value[1];
int currentCost = cost[row][col];
for (int i = 0; i < directions.GetLength(0); i++)
{
var nextRow = row + directions[i, 0];
var nextCol = col + directions[i, 1];
// grid[x][y] has 4 values
// 1 -> right, 2 <- left, 3 down, 4 up
var noAdditionalCost = grid[row][col] == (i + 1);
int newCost = currentCost + (noAdditionalCost ? 0 : 1);
if (nextRow >= 0 && nextCol >= 0 && nextRow < rows && nextCol < columns)
{
// current path is shorter one
if (newCost < cost[nextRow][nextCol])
{
cost[nextRow][nextCol] = newCost;
var nextPosition = new int[] { nextRow, nextCol };
if (noAdditionalCost)
{
list.AddFirst(nextPosition);
}
else
{
list.AddLast(nextPosition);
}
}
}
}
}
return cost[rows - 1][columns - 1];
}
}
