# 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]]))
