Leetcode discuss: 1293. Shortest Path in a Grid with Obstacles Elimination

 Here is the link. 

First practice - C# - BFS - obstacle as third dimension - Learning

Dec. 7, 2020
Introduction
It is challenge for me to train myself as a good thinker. I solved 590 algorithms, but I could not come out the idea using three dimension visited array to mark visit in BFS, obstracles can be used like third dimension. I still need to prove that the third dimension is working to prevent missing path in terms of getting minimum result. Right now I leave it as an assignment for the short future.

BFS approach
It is same as a classical BFS algorithm, and keep track of obstracles removed for current state.

public class Solution {
    /// <summary>
        /// Dec. 7, 2020
        /// study code
        /// https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/discuss/558572/Accepted-C-BFS-Solution
        /// </summary>
        /// <param name="grid"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public int ShortestPath(int[][] grid, int k)
        {
            int rows = grid.Length;
            int columns = grid[0].Length;

            // it is tough for me to figure out using three dimension - third dimension -
            // k obstacles to remove
            var visited = new bool[rows,columns,k + 1];

            var queue = new Queue<int[]>();
            queue.Enqueue(new int[]{0,0,k});

            visited[0, 0, k] = true;

            var directions = new int[4][];
            directions[0] = new int[]{-1, 0};  // top
            directions[1] = new int[]{0, 1}; // right
            directions[2] = new int[]{1, 0}; // down
            directions[3] = new int[]{0, -1}; // left
            
            int minimum = 0;
            while (queue.Count > 0)
            {
                int count = queue.Count;
                for (int i = 0; i < count; i++)
                {
                    var current = queue.Dequeue();
                    var row = current[0]; 
                    var col = current[1]; 
                    var left = current[2];

                    if (row == rows - 1 && col == columns - 1)
                    {
                        return minimum;
                    }                   
                    
                    foreach (var dir in directions)
                    {
                        var newRow = row + dir[0];
                        var newCol = col + dir[1];

                        if(newRow < 0 || newRow >= rows || newCol < 0 || newCol >= columns)
                        {
                            continue;
                        }

                        if (grid[newRow][newCol] == 0 && !visited[newRow, newCol, left])
                        {
                            // keep the same obstacles - but mark visit for left number
                            visited[newRow, newCol, left] = true;
                            queue.Enqueue(new int[]{newRow, newCol, left});
                            continue;
                        }

                        if (grid[newRow][newCol] == 1 && left != 0 && !visited[newRow, newCol, left - 1])
                        {
                            // replace current obstacle with 0, decrement variable left
                            visited[newRow, newCol, left - 1] = true;
                            queue.Enqueue(new int[]{newRow, newCol, left - 1});
                        }
                    }
                }

                minimum++;
            }

            return -1;
        }
}