[Python3] Modified Dijkstra. Detailed Solution.
Intuition\nDijkstra algorithm should always be considered first in shortest time/path questions.\n\n# Approach\nFirst observation:\nIf grid[0][1] <= 1 or grid[1
# Intuition\nDijkstra algorithm should always be considered first in shortest time/path questions.\n\n# Approach\nFirst observation:\nIf ```grid[0][1] <= 1``` or ```grid[1][0] <= 1```, then you can always reach the bottom right position because you can jump back and forth between the starting point ```(0, 0)``` and its neighbour.\n\nSecond observation:\nFor each position ```(r, c)```, you can visit it either at odd time or at even time, you won\'t be able to visit ```(r, c)``` at both an odd time and an even time. This is because if you jump out and jump in, it will take `2` seconds, so the time you can visit a cell should be `t`, `t + 2`, `t + 4`, ..., where all of them are all even or all odd, depends on whether `t` is even or not.\n\nFinally:\nIt\'s just the standard Dijkstra\'s algorithm, when you are about to visit a new cell `(r + dr, c + dc)`, assume the current time is `t`\n- if `t + 1` and `grid[r + dr][c + dc]` are of the same parity (e.g. both odd or both even), then earliest time you can visit `(r + dr, c + dc)` is either `t + 1` or `grid[r][c]`. \n- if `t + 1` and `grid[r + dr][c + dc]` are of different parity, then earliest time you can visit `(r + dr, c + dc)` is either `t + 1` or `grid[r][c] + 1`. Notice that we have `+1` here so that after that, `t + 1` and `grid[r][c] + 1` will have the same parity. \n\n# Complexity\n- Time complexity:\n$$O(mn log(mn))$$. Recall that for a standard Dijkstra algorithm, the time complexity is $$O((|V| + |E|) log V)$$, in our case, both $|V|$ and $|E|$ are $$O(mn)$$.\n\n- Space complexity:\n$$O(mn)$$. Recall that for a standard Dijkstra algorithm, the space complexity is $$O(|V| + |E|)$$, in our case, both $|V|$ and $|E|$ are $$O(mn)$$.\n\n# Code\n```\nclass Solution:\n    def minimumTime(self, grid: List[List[int]]) -> int:\n        if grid[0][1] > 1 and grid[1][0] > 1:\n            return -1\n\n        m, n = len(grid), len(grid[0])\n        heap = [(0, 0, 0)]\n        min_time = [[inf] * n for _ in range(m)]\n        min_time[0][0] = 0\n        \n        while heap:\n            curr_time, r, c = heappop(heap)\n            for dr, dc in [[-1, 0], [1, 0], [0, -1], [0, 1]]:\n                if 0 <= r + dr < m and 0 <= c + dc < n:\n                    if curr_time + 1 >= min_time[r + dr][c + dc]:\n                        continue\n                    else:\n                        if (curr_time + 1 - grid[r + dr][c + dc]) % 2 == 0:\n                            min_time[r + dr][c + dc] = max(curr_time + 1, grid[r + dr][c + dc])\n                        else:\n                            min_time[r + dr][c + dc] = max(curr_time + 1, grid[r + dr][c + dc] + 1)\n                        heappush(heap, (min_time[r + dr][c + dc], r + dr, c + dc))\n        return min_time[-1][-1]\n```
['Python3']