3627 Find Minimum Time To Reach Last Room I
3627 Find Minimum Time To Reach Last Room I
Find Minimum Time to Reach Last Room I 
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 exactly one second.
Return the minimum time to reach the room (n - 1, m - 1).
Two rooms are adjacent if they share a common wall, either horizontally or vertically.
Example 1:
Input: moveTime = [[0,4],[4,4]]
Output: 6
Explanation:
The minimum time required is 6 seconds.
1
2
At time t == 4, move from room (0, 0) to room (1, 0) in one second.
At time t == 5, move from room (1, 0) to room (1, 1) in one second.
Example 2:
Input: moveTime = [[0,0,0],[0,0,0]]
Output: 3
Explanation:
The minimum time required is 3 seconds.
1
2
3
At time t == 0, move from room (0, 0) to room (1, 0) in one second.
At time t == 1, move from room (1, 0) to room (1, 1) in one second.
At time t == 2, move from room (1, 1) to room (1, 2) in one second.
Example 3:
Input: moveTime = [[0,1],[1,2]]
Output: 3
Constraints:
1
2
3
2 <= n == moveTime.length <= 50
2 <= m == moveTime[i].length <= 50
0 <= moveTime[i][j] <= 109
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Solution:
def minTimeToReach(self, moveTime: List[List[int]]) -> int:
# idea is that start at end
# from end look for top and left
# T[0,0] = min(max(1, a[1,0]) + T[1,0] ,max(1, a[1,0]) + T[0,1])
# bfs should be ideal
rows, cols = len(moveTime), len(moveTime[0])
heap = [(0, 0, 0)] # (time, i, j)
visited = set()
while heap:
t, i, j = heapq.heappop(heap)
if (i, j) in visited:
continue
visited.add((i, j))
if i == rows - 1 and j == cols - 1:
return t
for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
ni, nj = i + di, j + dj
if 0 <= ni < rows and 0 <= nj < cols and (ni, nj) not in visited:
next_time = max(t + 1, moveTime[ni][nj] + 1)
heapq.heappush(heap, (next_time, ni, nj))
temp = [(0,0)]
t = 0
visited = frozenset()
@cache
def test(origin, t, visited):
visited = set(visited)
if origin[0] == len(moveTime)-1 and origin[1] == len(moveTime[0])-1:
return t
visited.add(origin)
a, b,c,d = float('inf'), float('inf'), float('inf'), float('inf')
if origin[0] + 1 < len(moveTime) and (origin[0] + 1, origin[1]) not in visited:
a = test((origin[0] + 1, origin[1]), max(t+1, moveTime[origin[0] + 1][origin[1]] + 1), frozenset(visited))
if origin[1] + 1 < len(moveTime[0]) and (origin[0] , origin[1]+1) not in visited:
b = test((origin[0], origin[1] + 1), max(t+1, moveTime[origin[0]][origin[1] + 1] + 1), frozenset(visited))
if origin[0] - 1 >= 0 and (origin[0] - 1, origin[1]) not in visited:
c = test((origin[0] - 1, origin[1]), max(t+1, moveTime[origin[0] - 1][origin[1]] + 1), frozenset(visited))
if origin[1] - 1 >= 0 and (origin[0], origin[1]-1) not in visited:
d = test((origin[0], origin[1] - 1), max(t+1, moveTime[origin[0]][origin[1] - 1] + 1), frozenset(visited))
visited.remove(origin)
return min(a,b,c,d)
return test((0,0), 0, visited)
while temp:
print(temp)
index = temp.pop(0)
if index in visited:
continue
t += 1
if index[0] + 1 < len(moveTime) :
t1 = moveTime[index[0] + 1][index[1]]
if t1 > t:
temp.append(index)
else:
visited.add((index[0] + 1, index[1]))
temp.append((index[0] + 1, index[1]))
if index[1] + 1 < len(moveTime[0]) :
t1 = moveTime[index[0]][index[1]+1]
if t1 > t:
temp.append(index)
else:
visited.add((index[0], index[1] + 1))
temp.append((index[0], index[1] + 1))
return t
This post is licensed under CC BY 4.0 by the author.