✅ Video | Beats 100% | Dijkstra's Algorithm
\n\nhttps://youtu.be/Kj98r8IgJOQ?si=t5CGvV0eYvsxm6dX\n\n# #1 Mod Dijkstra\'s Algorithm (Beats 95-100%)\npython3 []\nclass Solution:\n    def minimumTime(self, g
![image.png](https://assets.leetcode.com/users/images/8e17a01f-7982-4fc4-966e-07d3e864c0d6_1732661458.7958922.png)\n\nhttps://youtu.be/Kj98r8IgJOQ?si=t5CGvV0eYvsxm6dX\n\n# #1 Mod Dijkstra\'s Algorithm (Beats 95-100%)\n```python3 []\nclass Solution:\n    def minimumTime(self, grid: List[List[int]]) -> int:\n        MOVES = ((-1, 0), (0, 1), (1, 0), (0, -1))\n        \n        if grid[0][1] > 1 and grid[1][0] > 1:\n            return -1\n            \n        rows, cols = len(grid), len(grid[0])\n        pq = [(0, 0, 0)]  # time, row(x), col(y)\n        seen = [[False] * cols for _ in range(rows)]\n        seen[0][0] = True\n        \n        while pq:\n            time, row, col = heappop(pq)\n            \n            for dr, dc in MOVES:\n                newRow, newCol = row + dr, col + dc\n                \n                if (newRow < 0 or newRow >= rows or \n                    newCol < 0 or newCol >= cols or \n                    seen[newRow][newCol]):\n                    continue\n                \n                newTime = time + 1\n                if grid[newRow][newCol] > newTime:\n                    newTime += (grid[newRow][newCol] - time) // 2 * 2\n                \n                if newRow == rows - 1 and newCol == cols - 1:\n                    return newTime\n                    \n                seen[newRow][newCol] = True\n                heappush(pq, (newTime, newRow, newCol))\n                \n        return -1\n```\n```cpp []\nclass Solution {\npublic:\n    int minimumTime(vector<vector<int>>& grid) {\n        if (grid[0][1] > 1 && grid[1][0] > 1) return -1;\n        \n        int rows = grid.size();\n        int cols = grid[0].size();\n        \n        priority_queue<pair<int, pair<int, int>>, \n                      vector<pair<int, pair<int, int>>>, \n                      greater<pair<int, pair<int, int>>>> minHeap;\n        \n        minHeap.push({0, {0, 0}}); // time, row(x), col(y)\n        \n        vector<vector<int>> seen(rows, vector<int>(cols, 0));\n        seen[0][0] = 1;\n        \n        vector<pair<int, int>> moves = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};\n        \n        while (!minHeap.empty()) {\n            auto curr = minHeap.top();\n            int currTime = curr.first;\n            int currRow = curr.second.first;\n            int currCol = curr.second.second;\n            \n            minHeap.pop();\n            \n            if (currRow == rows - 1 && currCol == cols - 1) \n                return currTime;\n            \n            for (auto move : moves) {\n                int nextRow = move.first + currRow;\n                int nextCol = move.second + currCol;\n                \n                if (nextRow >= 0 && nextCol >= 0 && \n                    nextRow < rows && nextCol < cols && \n                    !seen[nextRow][nextCol]) {\n                    \n                    int waitTime = ((grid[nextRow][nextCol] - currTime) % 2 == 0) ? 1 : 0;\n                    int nextTime = max(currTime + 1, grid[nextRow][nextCol] + waitTime);\n                    \n                    minHeap.push({nextTime, {nextRow, nextCol}});\n                    seen[nextRow][nextCol] = 1;\n                }\n            }\n        }\n        return -1;\n    }\n};\n```\n```cpp [C++ v2]\nclass Solution {\npublic:\n    int minimumTime(vector<vector<int>>& grid) {\n        if (grid[0][1] > 1 && grid[1][0] > 1) return -1;\n        \n        int rows = grid.size();\n        int cols = grid[0].size();\n        int maxPos = rows * cols;\n        \n        priority_queue<pair<int, int>, \n                      vector<pair<int, int>>, \n                      greater<pair<int, int>>> minHeap;\n        \n        minHeap.push({0, 0}); // time, encoded position\n        \n        vector<bool> seen(maxPos, false); \n        seen[0] = true;\n        \n        const int moves[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};\n        \n        while (!minHeap.empty()) {\n            auto [currTime, pos] = minHeap.top();\n            int currRow = pos / cols;\n            int currCol = pos % cols;\n            \n            minHeap.pop();\n            \n            if (currRow == rows - 1 && currCol == cols - 1) \n                return currTime;\n            \n            for (const auto& move : moves) {\n                int nextRow = move[0] + currRow;\n                int nextCol = move[1] + currCol;\n                int nextPos = nextRow * cols + nextCol;\n                \n                if (nextRow >= 0 && nextCol >= 0 && \n                    nextRow < rows && nextCol < cols && \n                    !seen[nextPos]) {\n                    \n                    int waitTime = ((grid[nextRow][nextCol] - currTime) % 2 == 0) ? 1 : 0;\n                    int nextTime = max(currTime + 1, grid[nextRow][nextCol] + waitTime);\n                    \n                    minHeap.push({nextTime, nextPos});\n                    seen[nextPos] = true;\n                }\n            }\n        }\n        return -1;\n    }\n};\n```\n```java []\nclass Solution {\n    private static final int[][] MOVES = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};\n    \n    public int minimumTime(int[][] grid) {\n        int rows = grid.length;\n        int cols = grid[0].length;\n        \n        if (grid[0][1] > 1 && grid[1][0] > 1) {\n            return -1;\n        }\n        \n        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); \n        boolean[][] seen = new boolean[rows][cols];\n        \n        pq.offer(new int[]{0, 0, 0}); // time, row, col\n        seen[0][0] = true;\n        \n        while (!pq.isEmpty()) {\n            int[] curr = pq.poll();\n            int time = curr[0];\n            int row = curr[1];\n            int col = curr[2];\n            \n            for (int[] dir : MOVES) {\n                int newRow = row + dir[0];\n                int newCol = col + dir[1];\n                \n                if (newRow < 0 || newRow >= rows || \n                    newCol < 0 || newCol >= cols || \n                    seen[newRow][newCol]) {\n                    continue;\n                }\n                \n                int newTime = time + 1;\n                if (grid[newRow][newCol] > newTime) {\n                    int wait = ((grid[newRow][newCol] - newTime + 1) / 2) * 2;\n                    newTime += wait;\n                }\n                \n                if (newRow == rows - 1 && newCol == cols - 1) {\n                    return newTime;\n                }\n                \n                seen[newRow][newCol] = true;\n                pq.offer(new int[]{newTime, newRow, newCol});\n            }\n        }\n        \n        return -1;\n    }\n}\n```\n```csharp []\npublic class Solution {\n    private static readonly (int dr, int dc)[] MOVES = { (-1, 0), (0, 1), (1, 0), (0, -1) };\n    \n    public int MinimumTime(int[][] grid) {\n        if (grid[0][1] > 1 && grid[1][0] > 1) {\n            return -1;\n        }\n        \n        int rows = grid.Length;\n        int cols = grid[0].Length;\n        var pq = new PriorityQueue<(int time, int row, int col), int>();\n        pq.Enqueue((0, 0, 0), 0); // time, row, col, queue\n        \n        bool[][] seen = new bool[rows][];\n        for (int i = 0; i < rows; i++) {\n            seen[i] = new bool[cols];\n        }\n        seen[0][0] = true;\n        \n        while (pq.Count > 0) {\n            var (time, row, col) = pq.Dequeue();\n            \n            foreach (var (dr, dc) in MOVES) {\n                int newRow = row + dr;\n                int newCol = col + dc;\n                \n                if (newRow < 0 || newRow >= rows || \n                    newCol < 0 || newCol >= cols || \n                    seen[newRow][newCol]) {\n                    continue;\n                }\n                \n                int newTime = time + 1;\n                if (grid[newRow][newCol] > newTime) {\n                    newTime += ((grid[newRow][newCol] - time) / 2) * 2;\n                }\n                \n                if (newRow == rows - 1 && newCol == cols - 1) {\n                    return newTime;\n                }\n                \n                seen[newRow][newCol] = true;\n                pq.Enqueue((newTime, newRow, newCol), newTime);\n            }\n        }\n        \n        return -1;\n    }\n}\n```\n```golang []\ntype Cell struct {\n    time, row, col int\n}\n\ntype PriorityQueue []Cell\n\nfunc (pq PriorityQueue) Len() int { return len(pq) }\nfunc (pq PriorityQueue) Less(i, j int) bool { return pq[i].time < pq[j].time }\nfunc (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }\nfunc (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(Cell)) }\nfunc (pq *PriorityQueue) Pop() interface{} {\n    old := *pq\n    n := len(old)\n    item := old[n-1]\n    *pq = old[0 : n-1]\n    return item\n}\n\nfunc minimumTime(grid [][]int) int {\n    if grid[0][1] > 1 && grid[1][0] > 1 {\n        return -1\n    }\n    \n    rows, cols := len(grid), len(grid[0])\n    minHeap := &PriorityQueue{}\n    heap.Init(minHeap)\n    heap.Push(minHeap, Cell{0, 0, 0}) // time, row, col\n    \n    seen := make([][]int, rows)\n    for i := range seen {\n        seen[i] = make([]int, cols)\n    }\n    seen[0][0] = 1\n    \n    moves := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}\n    \n    for minHeap.Len() > 0 {\n        curr := heap.Pop(minHeap).(Cell)\n        currTime := curr.time\n        currRow := curr.row\n        currCol := curr.col\n        \n        if currRow == rows-1 && currCol == cols-1 {\n            return currTime\n        }\n        \n        for _, move := range moves {\n            nextRow := move[0] + currRow\n            nextCol := move[1] + currCol\n            \n            if nextRow >= 0 && nextCol >= 0 && \n               nextRow < rows && nextCol < cols && \n               seen[nextRow][nextCol] == 0 {\n                \n                waitTime := 0\n                if (grid[nextRow][nextCol]-currTime)%2 == 0 {\n                    waitTime = 1\n                }\n                nextTime := max(currTime+1, grid[nextRow][nextCol]+waitTime)\n                \n                heap.Push(minHeap, Cell{nextTime, nextRow, nextCol})\n                seen[nextRow][nextCol] = 1\n            }\n        }\n    }\n    return -1\n}\n\nfunc max(a, b int) int {\n    if a > b {\n        return a\n    }\n    return b\n}\n```\n```javascript [JS]\n// JavaScript\n\nvar minimumTime = function(grid) {\n    const MOVES = [[-1, 0], [0, 1], [1, 0], [0, -1]];\n    \n    if (grid[0][1] > 1 && grid[1][0] > 1) {\n        return -1;\n    }\n    \n    const rows = grid.length;\n    const cols = grid[0].length;\n    const seen = Array(rows).fill().map(() => Array(cols).fill(false));\n    seen[0][0] = true;\n    \n    const pq = new MinPriorityQueue({\n        priority: x => x[0]\n    });\n    pq.enqueue([0, 0, 0]); // time, row, col\n    \n    while (!pq.isEmpty()) {\n        const [time, row, col] = pq.dequeue().element;\n        \n        for (const [dr, dc] of MOVES) {\n            const newRow = row + dr;\n            const newCol = col + dc;\n            \n            if (newRow < 0 || newRow >= rows || \n                newCol < 0 || newCol >= cols || \n                seen[newRow][newCol]) {\n                continue;\n            }\n            \n            let newTime = time + 1;\n            if (grid[newRow][newCol] > newTime) {\n                newTime += Math.floor((grid[newRow][newCol] - time) / 2) * 2;\n            }\n            \n            if (newRow === rows - 1 && newCol === cols - 1) {\n                return newTime;\n            }\n            \n            seen[newRow][newCol] = true;\n            pq.enqueue([newTime, newRow, newCol]);\n        }\n    }\n    \n    return -1;\n};\n```\n```rust []\nuse std::collections::BinaryHeap;\nuse std::cmp::Reverse;\n\nimpl Solution {\n    pub fn minimum_time(grid: Vec<Vec<i32>>) -> i32 {\n        let moves = [(-1, 0), (0, 1), (1, 0), (0, -1)];\n        \n        if grid[0][1] > 1 && grid[1][0] > 1 {\n            return -1;\n        }\n        \n        let (rows, cols) = (grid.len(), grid[0].len());\n        let mut pq = BinaryHeap::new();\n        let mut seen = vec![vec![false; cols]; rows];\n        \n        pq.push(Reverse((0, 0, 0))); // (time, row, col)\n        seen[0][0] = true;\n        \n        while let Some(Reverse((time, row, col))) = pq.pop() {\n            for &(dr, dc) in &moves {\n                let new_row = row as i32 + dr;\n                let new_col = col as i32 + dc;\n                \n                if new_row < 0 || new_row >= rows as i32 || \n                   new_col < 0 || new_col >= cols as i32 ||\n                   seen[new_row as usize][new_col as usize] {\n                    continue;\n                }\n                \n                let mut new_time = time + 1;\n                let cell_value = grid[new_row as usize][new_col as usize];\n                \n                if cell_value > new_time {\n                    new_time += ((cell_value - time) / 2) * 2;\n                }\n                \n                if new_row as usize == rows - 1 && new_col as usize == cols - 1 {\n                    return new_time;\n                }\n                \n                seen[new_row as usize][new_col as usize] = true;\n                pq.push(Reverse((new_time, new_row as usize, new_col as usize)));\n            }\n        }\n        \n        -1\n    }\n}\n```\n```ruby []\ndef minimum_time(grid)\n    moves = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n    \n    return -1 if grid[0][1] > 1 && grid[1][0] > 1\n    \n    rows, cols = grid.length, grid[0].length\n    pq = [[0, 0, 0]] # time, row(x), col(y)\n    seen = Array.new(rows) { Array.new(cols, false) }\n    seen[0][0] = true\n    \n    while !pq.empty?\n        time, row, col = pq.shift\n        \n        moves.each do |dr, dc|\n            new_row, new_col = row + dr, col + dc\n            \n            next if new_row < 0 || new_row >= rows ||\n                   new_col < 0 || new_col >= cols ||\n                   seen[new_row][new_col]\n            \n            new_time = time + 1\n            if grid[new_row][new_col] > new_time\n                new_time += ((grid[new_row][new_col] - time) / 2) * 2\n            end\n            \n            return new_time if new_row == rows - 1 && new_col == cols - 1\n            \n            seen[new_row][new_col] = true\n            \n            insert_idx = pq.bsearch_index { |x| x[0] > new_time } || pq.length\n            pq.insert(insert_idx, [new_time, new_row, new_col])\n        end\n    end\n    \n    -1\nend\n```\n\n- Complexity:  Time O(RC * log(RC)) & Space O(RC) [R- rows, C - columns ]\n\n# #2 Mod Dijkstra\'s Algorithm (from video)\n\n\n```python3 []\nclass Solution:\n    def minimumTime(self, grid: List[List[int]]) -> int:\n        if min(grid[0][1], grid[1][0]) > 1:\n            return -1\n\n        min_heap = [(0, 0, 0)]  # (time, r, c)\n        ROWS, COLS = len(grid), len(grid[0])\n        visit = set()\n\n        while min_heap:\n            t, r, c = heapq.heappop(min_heap)\n            if (r, c) == (ROWS - 1, COLS - 1):\n                return t\n\n            nei = [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]\n            for nr, nc in nei:\n                if nr < 0 or nc < 0 or nr == ROWS or nc == COLS or (nr, nc) in visit:\n                    continue\n\n                wait = 0\n                if abs(grid[nr][nc] - t) % 2 == 0:\n                    wait = 1\n                n_time = max(grid[nr][nc] + wait, t + 1)\n                heapq.heappush(min_heap, (n_time, nr, nc))\n                visit.add((nr, nc))\n```\n```cpp []\nclass Solution {\npublic:\n    int minimumTime(vector<vector<int>>& grid) {\n        if (min(grid[0][1], grid[1][0]) > 1) {\n            return -1;\n        }\n        \n        int ROWS = grid.size(), COLS = grid[0].size();\n        priority_queue<vector<int>, vector<vector<int>>, greater<>> minHeap;\n        minHeap.push({0, 0, 0}); // {time, r, c}\n        set<pair<int, int>> visit;\n        \n        while (!minHeap.empty()) {\n            auto curr = minHeap.top();\n            minHeap.pop();\n            int t = curr[0], r = curr[1], c = curr[2];\n            \n            if (r == ROWS - 1 && c == COLS - 1) {\n                return t;\n            }\n            \n            vector<pair<int, int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n            for (auto [dr, dc] : dirs) {\n                int nr = r + dr, nc = c + dc;\n                if (nr < 0 || nc < 0 || nr == ROWS || nc == COLS || \n                    visit.count({nr, nc})) {\n                    continue;\n                }\n                \n                int wait = (abs(grid[nr][nc] - t) % 2 == 0) ? 1 : 0;\n                int nTime = max(grid[nr][nc] + wait, t + 1);\n                minHeap.push({nTime, nr, nc});\n                visit.insert({nr, nc});\n            }\n        }\n        return -1;\n    }\n};\n```\n```java []\nclass Solution {\n    public int minimumTime(int[][] grid) {\n        if (Math.min(grid[0][1], grid[1][0]) > 1) {\n            return -1;\n        }\n        \n        int ROWS = grid.length, COLS = grid[0].length;\n        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);\n        minHeap.offer(new int[]{0, 0, 0}); // {time, r, c}\n        Set<String> visit = new HashSet<>();\n        \n        while (!minHeap.isEmpty()) {\n            int[] curr = minHeap.poll();\n            int t = curr[0], r = curr[1], c = curr[2];\n            \n            if (r == ROWS - 1 && c == COLS - 1) {\n                return t;\n            }\n            \n            int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n            for (int[] dir : dirs) {\n                int nr = r + dir[0], nc = c + dir[1];\n                String key = nr + "," + nc;\n                \n                if (nr < 0 || nc < 0 || nr == ROWS || nc == COLS || \n                    visit.contains(key)) {\n                    continue;\n                }\n                \n                int wait = (Math.abs(grid[nr][nc] - t) % 2 == 0) ? 1 : 0;\n                int nTime = Math.max(grid[nr][nc] + wait, t + 1);\n                minHeap.offer(new int[]{nTime, nr, nc});\n                visit.add(key);\n            }\n        }\n        return -1;\n    }\n}\n```\n```csharp []\npublic class Solution {\n    public int MinimumTime(int[][] grid) {\n        if (Math.Min(grid[0][1], grid[1][0]) > 1) {\n            return -1;\n        }\n        \n        int ROWS = grid.Length, COLS = grid[0].Length;\n        var minHeap = new PriorityQueue<(int t, int r, int c), int>();\n        minHeap.Enqueue((0, 0, 0), 0); // (time, r, c)\n        var visit = new HashSet<string>();\n        \n        while (minHeap.Count > 0) {\n            var (t, r, c) = minHeap.Dequeue();\n            \n            if (r == ROWS - 1 && c == COLS - 1) {\n                return t;\n            }\n            \n            var dirs = new[] { (1, 0), (-1, 0), (0, 1), (0, -1) };\n            foreach (var (dr, dc) in dirs) {\n                int nr = r + dr, nc = c + dc;\n                string key = $"{nr},{nc}";\n                \n                if (nr < 0 || nc < 0 || nr == ROWS || nc == COLS || \n                    visit.Contains(key)) {\n                    continue;\n                }\n                \n                int wait = (Math.Abs(grid[nr][nc] - t) % 2 == 0) ? 1 : 0;\n                int nTime = Math.Max(grid[nr][nc] + wait, t + 1);\n                minHeap.Enqueue((nTime, nr, nc), nTime);\n                visit.Add(key);\n            }\n        }\n        return -1;\n    }\n}\n```\n```golang []\npackage main\n\nimport (\n    "container/heap"\n    "fmt"\n)\n\ntype MinHeap [][]int\n\nfunc (h MinHeap) Len() int           { return len(h) }\nfunc (h MinHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }\nfunc (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }\n\nfunc (h *MinHeap) Push(x interface{}) {\n    *h = append(*h, x.([]int))\n}\n\nfunc (h *MinHeap) Pop() interface{} {\n    old := *h\n    n := len(old)\n    x := old[n-1]\n    *h = old[0 : n-1]\n    return x\n}\n\nfunc abs(x int) int {\n    if x < 0 {\n        return -x\n    }\n    return x\n}\nfunc min(a, b int) int {\n    if a < b {\n        return a\n    }\n    return b\n}\n\nfunc max(a, b int) int {\n    if a > b {\n        return a\n    }\n    return b\n}\n\nfunc minimumTime(grid [][]int) int {\n    if min(grid[0][1], grid[1][0]) > 1 {\n        return -1\n    }\n    \n    rows, cols := len(grid), len(grid[0])\n    minHeap := &MinHeap{}\n    heap.Init(minHeap)\n    heap.Push(minHeap, []int{0, 0, 0}) // time, r, c\n    visited := make(map[string]bool)\n    \n    dirs := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}\n    \n    for minHeap.Len() > 0 {\n        curr := heap.Pop(minHeap).([]int)\n        t, r, c := curr[0], curr[1], curr[2]\n        \n        if r == rows-1 && c == cols-1 {\n            return t\n        }\n        \n        for _, dir := range dirs {\n            nr, nc := r+dir[0], c+dir[1]\n            key := fmt.Sprintf("%d,%d", nr, nc)\n            \n            if nr < 0 || nc < 0 || nr == rows || nc == cols || visited[key] {\n                continue\n            }\n            \n            wait := 0\n            if abs(grid[nr][nc]-t)%2 == 0 {\n                wait = 1\n            }\n            nTime := max(grid[nr][nc]+wait, t+1)\n            heap.Push(minHeap, []int{nTime, nr, nc})\n            visited[key] = true\n        }\n    }\n    return -1\n}\n```\n```javascript [JS]\n// JavaScript\n\nvar minimumTime = function(grid) {\n    if (Math.min(grid[0][1], grid[1][0]) > 1) {\n        return -1;\n    }\n    \n    const ROWS = grid.length;\n    const COLS = grid[0].length;\n    const minHeap = new MinPriorityQueue({ priority: x => x[0] });\n    minHeap.enqueue([0, 0, 0]); // [time, r, c]\n    const visited = new Set();\n    \n    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];\n    \n    while (!minHeap.isEmpty()) {\n        const [t, r, c] = minHeap.dequeue().element;\n        \n        if (r === ROWS - 1 && c === COLS - 1) {\n            return t;\n        }\n        \n        for (const [dr, dc] of dirs) {\n            const nr = r + dr;\n            const nc = c + dc;\n            const key = `${nr},${nc}`;\n            \n            if (nr < 0 || nc < 0 || nr === ROWS || nc === COLS || visited.has(key)) {\n                continue;\n            }\n            \n            const wait = Math.abs(grid[nr][nc] - t) % 2 === 0 ? 1 : 0;\n            const nTime = Math.max(grid[nr][nc] + wait, t + 1);\n            minHeap.enqueue([nTime, nr, nc], nTime);\n            visited.add(key);\n        }\n    }\n    return -1;\n};\n```\n```typescript [TS]\n// TypeScript\n\nfunction minimumTime(grid: number[][]): number {\n    if (Math.min(grid[0][1], grid[1][0]) > 1) {\n        return -1;\n    }\n    \n    const ROWS = grid.length;\n    const COLS = grid[0].length;\n    const minHeap = new MinPriorityQueue({ priority: x => x[0] });\n    minHeap.enqueue([0, 0, 0]); // [time, r, c]\n    const visited = new Set<string>();\n    \n    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];\n    \n    while (!minHeap.isEmpty()) {\n        const [t, r, c] = minHeap.dequeue().element;\n        \n        if (r === ROWS - 1 && c === COLS - 1) {\n            return t;\n        }\n        \n        for (const [dr, dc] of dirs) {\n            const nr = r + dr;\n            const nc = c + dc;\n            const key = `${nr},${nc}`;\n            \n            if (nr < 0 || nc < 0 || nr === ROWS || nc === COLS || visited.has(key)) {\n                continue;\n            }\n            \n            const wait = Math.abs(grid[nr][nc] - t) % 2 === 0 ? 1 : 0;\n            const nTime = Math.max(grid[nr][nc] + wait, t + 1);\n            minHeap.enqueue([nTime, nr, nc]);\n            visited.add(key);\n        }\n    }\n    return -1;\n}\n```\n\n- Complexity:  Time O(RC * log(RC)) & Space O(RC) [R- rows, C - columns ]\n\n\n\n\n# Explanation\n\n\n---\n\n## Intuition\n\n![29tlu.png](https://assets.leetcode.com/users/images/a74ad09b-ff59-4e18-b8c7-7bdd36f70f5a_1732841837.5389009.png)\n\n\n![29tlu2.png](https://assets.leetcode.com/users/images/3d6c8fef-36f5-40c3-837e-bc1445edd98a_1732845159.0596716.png)\n\n\n![29tlu3.png](https://assets.leetcode.com/users/images/3dec9bff-bbed-4359-a3cd-8917e17db8fc_1732845517.3856816.png)\n\n\n\n\n## Graph Theory\n\n- (IMO) the best explaining Video on graph from Google engineer.\nhttps://youtu.be/09_LlHjoEiY?si=EKU-b9pAafWX1Wea\n\n####  [Interview Questions and Answers Repository](https://github.com/RooTinfinite/Interview-questions-and-answers)\n\n![image.png](https://assets.leetcode.com/users/images/9dc1b265-b175-4bf4-bc6c-4b188cb79220_1728176037.4402142.png)
['C++', 'Java', 'Go', 'TypeScript', 'Python3', 'Rust', 'Ruby', 'JavaScript', 'C#']