Find Minimum Time to Reach Last Room II
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.
- Two seconds for the next move.
- These durations keep alternating between one and two seconds.
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
7The minimum time required is 7 seconds: wait until
t == 4, move to (1, 0) in one second, then move to (1, 1) in two seconds.Example 2
Input
moveTime = [[0,0,0,0],[0,0,0,0]]Output
6The minimum time required is 6 seconds by moving along the bottom row with move durations alternating between one and two seconds.
Constraints
- 2 <= n == moveTime.length <= 750
- 2 <= m == moveTime[i].length <= 750
- 0 <= moveTime[i][j] <= 10^9