Python Dijkstra, Code w/ Notes
Code\npython3 []\nclass Solution:\n    def minimumTime(self, grid: List[List[int]]) -> int:\n        # if no cells to move at start, then invalid\n        if gr
# Code\n```python3 []\nclass Solution:\n    def minimumTime(self, grid: List[List[int]]) -> int:\n        # if no cells to move at start, then invalid\n        if grid[0][1] > 1 and grid[1][0] > 1:\n            return -1\n\n        m, n = len(grid), len(grid[0]) # row and cols\n        \n        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # up, down, left right\n        \n        heap = [(0, 0, 0)] # starting time, x, y\n\n        visited = [[False] * n for _ in range(m)] # set all cells to not visited except start\n        visited[0][0] = True\n        \n        while heap:\n            time, x, y = heapq.heappop(heap) # get cell w/ lowest time\n            \n            # if current cell is bottom right, then return time\n            if x == m - 1 and y == n - 1:\n                return time\n            \n            # explore all directions of current cell\n            for dx, dy in directions:\n                nx, ny = x + dx, y + dy\n                \n                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:\n                    visited[nx][ny] = True \n\n                    # can immediately visit if cell time <= current time + 1\n                    if grid[nx][ny] <= time + 1:\n                        heapq.heappush(heap, (time + 1, nx, ny))\n\n                    # can\'t visit right now, add w/ time for when visit possible\n                    else:\n                        diff = grid[nx][ny] - time # wait time before can visit\n\n                        if diff % 2 == 1: # wait time is odd, cell time = time + 1\n                            heapq.heappush(heap, (grid[nx][ny], nx, ny))\n\n                            # ex. dif = 3, path = 0 -> 1 -> 2 -> 1 -> 4, time = 4\n                            # 0 - -\n                            # 1 4 -\n                            # 2 - -\n                            \n                        else: # wait time is even, cell time = time + 1 + 1\n                            heapq.heappush(heap, (grid[nx][ny] + 1, nx, ny))\n\n                            # ex. dif = 2, path = 0 -> 1 -> 2 -> 1 -> 3, time = 4\n                            # 0 - -\n                            # 1 3 -\n                            # 2 - -\n        \n        # invalid path\n        return -1\n\n```
['Python3']