2577. Minimum Time to Visit a Cell In a Grid ## 思路 每個點可以重複走, 所以只有grid[0][1], grid[1][0] 大於1的時候 才回傳-1 用heap+BFS檢查沒走過的點 如果當前時間是t, 下一步 (nr, nc) 1. grid[nr][nc] <= t+1 --> t+1 2. grid[nr][nc] > t 往回重複走 如果diff為偶數要再多1秒 e.g grid[nr][nc] = t+4 --> t+5 ## Code ```python class Solution: def minimumTime(self, grid: List[List[int]]) -> int: if grid[0][1] > 1 and grid[1][0] > 1: return -1 len_r, len_c = len(grid), len(grid[0]) seen = set() heap = [(grid[0][0], 0, 0)] while heap: time, r, c = heapq.heappop(heap) if r == len_r-1 and c == len_c-1: return time if (r, c) in seen: continue seen.add((r, c)) for nr, nc in (r+1, c), (r-1, c), (r, c-1), (r, c+1): if 0 <= nr < len_r and 0 <= nc < len_c and (nr, nc) not in seen: next_time = time + 1 if grid[nr][nc] > next_time: diff = grid[nr][nc] - time next_time += diff - (diff & 1) heapq.heappush(heap, (next_time, nr, nc)) ``` -- ※ 發信站: 批踢踢實業坊(web-ptt.org.tw), 來自: 94.156.205.64 (臺灣) ※ 文章網址: https://web-ptt.org.tw/Marginalman/M.1732930011.A.3AC