BFS with Min Heap (Optimized)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(m * n * log (m * n))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(m * n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def minimumTime(self, grid: List[List[int]]) -> int:\n        # base\n        if grid[0][1] > 1 and grid[1][0] > 1:\n            return -1\n\n        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n        m, n = len(grid), len(grid[0])\n\n        minhpq = [(0, 0, 0)]       # stores (time, i, j) increasngly\n        visited = {(0, 0)}         # trace back visited cell\n\n        while minhpq:\n            time, i, j = heappop(minhpq)\n\n            # stop; found a solution\n            if i == m - 1 and j == n - 1:\n                return time\n\n            for di, dj in dirs:\n                di, dj = i + di, j + dj\n                \n                # pass; infeasible or seen before\n                if di < 0 or di >= m or dj < 0 or dj >= n or (di, dj) in visited:\n                    continue\n\n                # wait is at max 1 to move from (i, j) to (di, dj)\n                wait = 1 if (grid[di][dj] - time) % 2 == 0 else 0\n\n                # take the max for the next possible valid time\n                next_time = max(time + 1, grid[di][dj] + wait)\n\n                # push the new cell into min heap\n                heappush(minhpq, (next_time, di, dj))\n                visited.add((di, dj))\n\n        return -1\n```
['Array', 'Breadth-First Search', 'Graph', 'Heap (Priority Queue)', 'Matrix', 'Shortest Path', 'Python3']