aboutsummaryrefslogtreecommitdiff
path: root/find_min_time_reach_last_room1.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-05-06 22:25:43 -0600
committerJack Sangdahl <[email protected]>2025-05-06 22:25:43 -0600
commit3521f588bcb62799cd10de0acc7eb294d1a58b26 (patch)
tree3afc7b7a97982b919ece9b1055396b3ee08a138c /find_min_time_reach_last_room1.py
parent60f186c6df107c7632d37fe8bde204fb9ba54b6c (diff)
downloadleetcode-3521f588bcb62799cd10de0acc7eb294d1a58b26.tar.gz
leetcode-3521f588bcb62799cd10de0acc7eb294d1a58b26.zip
3341. find minimum time to reach last room 1
Diffstat (limited to 'find_min_time_reach_last_room1.py')
-rw-r--r--find_min_time_reach_last_room1.py41
1 files changed, 41 insertions, 0 deletions
diff --git a/find_min_time_reach_last_room1.py b/find_min_time_reach_last_room1.py
new file mode 100644
index 0000000..3ce1848
--- /dev/null
+++ b/find_min_time_reach_last_room1.py
@@ -0,0 +1,41 @@
+# 3341. Find Minimum Time to Reach Last Room I
+import heapq
+
+"""
+there is a dungeo 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 at '(0, 0)' at time 't = 0' and can move to an anyacent room.
+moving between anyacent rooms takes exactly one second. 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)]
+ h = [[0, 1, 0, 0]]
+ moveTime[0][0] = -1
+ while h:
+ t, c, i, j = heapq.heappop(h)
+ if t >= dp[i][j]:
+ continue
+ if i == n - 1 and j == m - 1:
+ return t
+ dp[i][j] = t
+ for nx, ny in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
+ x, y = i + nx, j + ny
+ if 0 <= x < n and 0 <= y < m and dp[x][y] == "inf":
+ heapq.heappush(h, [max(moveTime[x][y] + c, t + c), 2 - 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]]))
+ print(obj.minTimeToReach(moveTime=[[0, 1], [1, 2]]))