Dijkstra’s Algorithm
Code

# Code
```python3 []
class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        # edge case
        if grid[0][1] > 1 and grid[1][0] > 1:
            return -1
        # initialize
        m, n = len(grid), len(grid[0])
        trans = [(0,1),(0,-1),(1,0),(-1,0)]

        INF = float('inf')
        time_cost = [[INF] * n for _ in range(m)]
        # Queue
        minheap = []
        heapq.heappush(minheap,(0,0,0))  # t, i, j
        time_cost[0][0] = 0
        # main loop
        while minheap:
            time, x, y = heapq.heappop(minheap)

            if x == m-1 and y == n-1:
                return time
            
            if time > time_cost[x][y]:
                continue

            arrival = time + 1
            for transx, transy in trans:
                nx, ny = transx + x, transy + y
                if 0 <= nx < m and 0 <= ny < n:
                    # no need to wait
                    if arrival >= grid[nx][ny]:
                        newtime = arrival

                    # need to wait
                    else:
                        newtime = grid[nx][ny] + (1 if (grid[nx][ny] - arrival) % 2 == 1 else 0)

                    # update cost array
                    if time_cost[nx][ny] > newtime:
                        time_cost[nx][ny] = newtime
                        heapq.heappush(minheap,(time_cost[nx][ny], nx, ny))           
        return -1
```
['Array', 'Heap (Priority Queue)', 'Python3']