2577. Minimum Time to Visit a Cell In a Grid
Approach
Dijkstra with waiting: if arrival parity mismatches cell time, wait one step.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
BFS explores nodes level by level, guaranteeing the shortest path in unweighted graphs. Use a Queue<T> and a visited set. Classic applications: shortest path, level-order tree traversal, multi-source distance (e.g., "01 matrix"), and word ladder transformations.
Graph algorithms model relationships between entities. Core algorithms: DFS/BFS for traversal, Dijkstra for weighted shortest path, Bellman-Ford for negative weights, Floyd-Warshall for all-pairs, and Kruskal/Prim for minimum spanning trees. Represent graphs as adjacency lists (Dictionary<int, List<int>>) for efficiency.
// Approach: Dijkstra with waiting: if arrival parity mismatches cell time, wait one step.
// Time: O(mn log(mn)) Space: O(mn)
public class Solution
{
public int MinimumTime(int[][] grid)
{
if (grid[0][1] > 1 && grid[1][0] > 1)
return -1;
int[][] dirs = new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 }, new int[] { 0, -1 }, new int[] { -1, 0 } };
int m = grid.Length;
int n = grid[0].Length;
var minHeap = new PriorityQueue<int[], int[]>(Comparer<int[]>.Create((a, b) => a[0].CompareTo(b[0])));
int[] first = new int[] { 0, 0, 0 };
minHeap.Enqueue(first, first); // (time, i, j)
bool[,] seen = new bool[m, n];
seen[0, 0] = true;
while (minHeap.Count > 0)
{
int time = minHeap.Peek()[0];
int i = minHeap.Peek()[1];
int j = minHeap.Peek()[2];
minHeap.Dequeue();
if (i == m - 1 && j == n - 1)
return time;
foreach (var dir in dirs)
{
int x = i + dir[0];
int y = j + dir[1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (seen[x, y])
continue;
int extraWait = (grid[x][y] - time) % 2 == 0 ? 1 : 0;
int nextTime = Math.Max(time + 1, grid[x][y] + extraWait);
int[] nextVal = new int[] { nextTime, x, y };
minHeap.Enqueue(nextVal, nextVal);
seen[x, y] = true;
}
}
throw new ArgumentException();
}
}