weekly contest 422。
竟然用 n x m 而不是慣用的 m x n,感覺不太舒服。

題目

有個迷宮有 n x m 個房間,以網格狀表示。

輸入 n x m 二維整數陣列 moveTime,其中 moveTime[i][j] 代表你在這個時間以後才可以移動前往
你在時間 t = 0 時從房間 (0, 0) 出發,每次可以移動到一個相鄰的房間。
每次移動耗時為 1 秒。

求抵達房間 (n - 1, m - 1) 所需的最少時間。

若兩個房間同享一個牆壁 (水平或垂直皆可),則視為相鄰的。

解法

看到最短路、邊權不同,就知道是 djikstra。
直接在二維矩陣上求最短路即可。

時間複雜度 O(NM log NM)。
空間複雜度 O(NM)。

class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        N, M = len(moveTime), len(moveTime[0])

        vis = [[False] * M for _ in range(N)]
        dist = [[inf] * M for _ in range(N)]
        heap = [[0, 0, 0]] # cost, r, c
        while heap:
            cost, r, c = heappop(heap)
            if cost > dist[r][c]:
                continue
            dist[r][c] = cost
            for dx, dy in pairwise([0,1,0,-1,0]):
                rr, cc = r+dx, c+dy
                if 0 <= rr < N and 0 <= cc < M:
                    new_cost = max(cost, moveTime[rr][cc]) + 1
                    if new_cost < dist[rr][cc]:
                        dist[rr][cc] = new_cost  # important pruning
                        heappush(heap, [new_cost, rr, cc])

        return dist[-1][-1]