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

minTimeToReach.js

/**
 * @param {number[][]} moveTime
 * @return {number}
 */
var minTimeToReach = function(moveTime) {
    const n = moveTime.length, m = moveTime[0].length;

    // Distance array initialized with Infinity, representing minimum time to reach each cell
    const d = Array.from({ length: n }, () => Array(m).fill(Infinity));

    // Possible movement directions: up, down, left, right
    const dirs = [
        [1, 0],  // Down
        [-1, 0], // Up
        [0, 1],  // Right
        [0, -1], // Left
    ];

    // Priority queue to process nodes in increasing order of distance
    const q = new PriorityQueue((a, b) => a.dist - b.dist);
    
    // Starting at (0,0) with distance 0
    q.enqueue({ x: 0, y: 0, dist: 0, move: 0 });
    d[0][0] = 0;

    while (!q.isEmpty()) {
        const { x, y, dist, move } = q.dequeue();

        // If we reach the bottom-right corner, return the total time taken
        if (x === n - 1 && y === m - 1) {
            return dist;
        }

        // Explore all four directions
        for (const [dx, dy] of dirs) {
            const nx = x + dx, ny = y + dy;

            // Skip out-of-bound positions
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

            // Calculate waiting time ensuring we only move after the cell's required move time
            const waitTime = Math.max(dist, moveTime[nx][ny]);

            // Determine travel time (1 if even move count, 2 otherwise)
            const travelTime = (move % 2 === 0) ? 1 : 2;
            const newDist = waitTime + travelTime;

            // Update distance if a shorter path is found
            if (newDist < d[nx][ny]) {
                d[nx][ny] = newDist;
                q.enqueue({ x: nx, y: ny, dist: newDist, move: move + 1 });
            }
        }
    }

    // If destination is unreachable, return -1
    return -1;
};