diff options
Diffstat (limited to 'find_min_time_reach_last_room2.py')
-rw-r--r-- | find_min_time_reach_last_room2.py | 43 |
1 files changed, 43 insertions, 0 deletions
diff --git a/find_min_time_reach_last_room2.py b/find_min_time_reach_last_room2.py new file mode 100644 index 0000000..11bf407 --- /dev/null +++ b/find_min_time_reach_last_room2.py @@ -0,0 +1,43 @@ +# 3342. Find Minimum Time to Reach Last Room II +import heapq + +""" +there is a dungeon with 'n x m' rooms arranged as a grid. you are given a 2d +array 'moveTime' of size 'n x m' where 'moveTime[i][j]' represents the +minimum time in seconds when you can start moving to that room. you start +from the room '(0, 0)' at time 't = 0' and can move to an adjacent room. +moving between adjacent rooms takes one second for one move and two seconds +for the next, alternating between the two. return the minimum time to reach +the room '(n - 1, m - 1)'. +""" + + +class Solution(object): + def minTimeToReach(self, moveTime): + """ + :type moveTime: List[List[int]] + :rtype: int + """ + n, m = len(moveTime), len(moveTime[0]) + dp = [["inf"] * m for i in range(n)] + heap = [[0, 0, 0]] + moveTime[0][0] = -1 + while heap: + t, i, j = heapq.heappop(heap) + if t >= dp[i][j]: + continue + if i == n - 1 and j == m - 1: + return t + dp[i][j] = t + for di, dj in [[1, 0], [0, 1], [-1, 0], [0, -1]]: + x, y = i + di, j + dj + c = (i + j) % 2 + 1 + if 0 <= x < n and 0 <= y < m and dp[x][y] == "inf": + heapq.heappush(heap, [max(moveTime[x][y], t) + c, x, y]) + + +if __name__ == "__main__": + obj = Solution() + print(obj.minTimeToReach(moveTime=[[0, 4], [4, 4]])) + print(obj.minTimeToReach(moveTime=[[0, 0, 0, 0], [0, 0, 0, 0]])) + print(obj.minTimeToReach(moveTime=[[0, 1], [1, 2]])) |