[Python] BFS with priority queue; Explained
The BFS can be used to solve the minimum time or minimum length problem.\n\n(1) In this problem, we must move to a different cell every second. Thus, the only c
The BFS can be used to solve the minimum time or minimum length problem.\n\n(1) In this problem, we must move to a different cell every second. Thus, the only case that we cannot reach the bottom right cell is that all the cells next to (0, 0) has required visit time larger than 1. If we have more than 2 visited cells, we can move back and forth so that the required visit time can meet.\n\n(2) Since we are moving back and forth, the minimum increment of time is 2. If the difference between the required visit time of next cell and the current time is multiple of 2, we need add one more second before we can reach the next cell.\n\n(3) Sort all the cells in a priority queue based on the next visit time, so that we can always visit the cell using the minimum time.\n\nWhenever, we reach the bottom right cell, we can return the visiting time.\n\n```\nclass Solution:\n    def minimumTime(self, grid: List[List[int]]) -> int:\n        nrow = len(grid)\n        ncol = len(grid[0])\n        \n        visited = set()\n        visit_queue = [(0, 0, 0)]\n        visited.add((0, 0))\n        \n        ans = -1\n        while visit_queue:\n            visit_time, r, c = heapq.heappop(visit_queue)\n            if r == nrow - 1 and c == ncol - 1:\n                ans = visit_time\n                break\n            \n            for ncell in {(0, 1), (1, 0), (0, -1), (-1, 0)}:\n                nr = r + ncell[0]\n                nc = c + ncell[1]\n                if nr >= 0 and nr < nrow and nc >= 0 and nc < ncol and (nr, nc) not in visited:\n                    if grid[nr][nc] <= visit_time + 1:\n                        heapq.heappush(visit_queue, (visit_time + 1, nr, nc))\n                        visited.add((nr, nc))\n                    elif len(visited) >= 2:\n                        if (grid[nr][nc] - visit_time - 1) % 2:\n                            heapq.heappush(visit_queue, (grid[nr][nc] + 1, nr, nc))\n                        else:\n                            heapq.heappush(visit_queue, (grid[nr][nc], nr, nc))\n                        visited.add((nr, nc))\n        \n        return ans\n```
['Python3']