C# Solution for Minimum Time to Visit a Cell In a Grid Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem can be thought of as finding the shortest path in a grid, where each cell h
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem can be thought of as finding the shortest path in a grid, where each cell has a \u201Cgate\u201D that only opens at a specific time (grid[row][col]). You start at the top-left cell at time 0 and must reach the bottom-right cell while navigating through cells in four directions (up, down, left, right). Moving takes exactly 1 second, and you may have to wait at certain cells if the required time (grid[row][col]) is not met. The challenge is to minimize the total time taken.\n\nThis is akin to a shortest-path problem in a weighted graph, where the edge weights are dynamic and depend on the time synchronization needed to move to the next cell.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tDijkstra-like Algorithm:\n\t\u2022\tUse a priority queue (min-heap) to always explore the cell that can be reached in the shortest time.\n\t\u2022\tEach entry in the queue represents (time, row, col) where time is the earliest time you can reach that cell.\n2.\tPriority Queue Setup:\n\t\u2022\tStart from (0, 0) with time = 0.\n\t\u2022\tPush the starting cell into the priority queue with an initial time of 0.\n3.\tMovement Logic:\n\t\u2022\tAt each step, dequeue the cell (time, row, col) with the smallest time.\n\t\u2022\tTry to move in all four possible directions (up, down, left, right).\n\t\u2022\tCalculate the nextTime as time + 1.\n\t\u2022\tIf nextTime < grid[newRow][newCol], check whether the difference between grid[newRow][newCol] and nextTime is even or odd:\n\t\u2022\tIf even, move at exactly grid[newRow][newCol].\n\t\u2022\tIf odd, wait an extra second to synchronize, and move at grid[newRow][newCol] + 1.\n4.\tVisited Array:\n\t\u2022\tUse a visited 2D array to track cells that have already been processed to avoid redundant calculations.\n5.\tTermination:\n\t\u2022\tIf the bottom-right cell (m-1, n-1) is reached, return the time.\n\t\u2022\tIf all possible cells have been processed and (m-1, n-1) has not been reached, return -1.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n1.\tPriority Queue Operations:\n\t\u2022\tThe priority queue holds up to m x n elements at any time.\n\t\u2022\tEach insertion or removal from the queue takes O(log(m x n)) time.\n2.\tProcessing Each Cell:\n\t\u2022\tEach cell is processed once, and each can be pushed into the priority queue once.\n\t\u2022\tHence, total insertions and deletions are O(m x n).\n\nThus, the total time complexity is O(m x n log(m x n)).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n1.\tPriority Queue:\n\t\u2022\tThe queue stores up to m x n cells.\n2.\tVisited Array:\n\t\u2022\tThe visited array is of size m x n.\n\nThus, the total space complexity is O(m x n).\n\n# Code\n```csharp []\npublic class Solution {\n    public int MinimumTime(int[][] grid) {\n        int m = grid.Length;\n        int n = grid[0].Length;\n\n        if (grid[0][1] > 1 && grid[1][0] > 1) {\n            return -1;\n        }\n\n        var pq = new PriorityQueue<(int time, int row, int col), int>();\n        pq.Enqueue((0, 0, 0), 0);\n\n        bool[,] visited = new bool[m, n];\n        int[][] directions = new int[][] {\n            new int[] {0, 1}, \n            new int[] {1, 0},  \n            new int[] {0, -1}, \n            new int[] {-1, 0}  \n        };\n\n        while (pq.Count > 0) {\n            var (time, row, col) = pq.Dequeue();\n\n            if (row == m - 1 && col == n - 1) {\n                return time;  \n            }\n\n            if (visited[row, col]) continue;\n            visited[row, col] = true;\n\n            foreach (var dir in directions) {\n                int newRow = row + dir[0];\n                int newCol = col + dir[1];\n\n                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {\n                    int nextTime = time + 1;\n                    int requiredTime = grid[newRow][newCol];\n\n                    if (nextTime < requiredTime) {\n                        int wait = (requiredTime - nextTime) % 2 == 0 ? 0 : 1;\n                        nextTime = requiredTime + wait;\n                    }\n\n                    if (!visited[newRow, newCol]) {\n                        pq.Enqueue((nextTime, newRow, newCol), nextTime);\n                    }\n                }\n            }\n        }\n\n        return -1;\n    }\n}\n```
['C#']