3341. Find Minimum Time to Reach Last Room I

Description

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.

• 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.

• 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:

• 2 <= n == moveTime.length <= 50
• 2 <= m == moveTime[i].length <= 50
• 0 <= moveTime[i][j] <= 109

 

Solutions

Solution: Dijkstra's Algorithm

• Time complexity: O(mnlogmn)
• Space complexity: O(mn)

 

JavaScript

/**
 * @param {number[][]} moveTime
 * @return {number}
 */
const minTimeToReach = function (moveTime) {
  const m = moveTime.length;
  const n = moveTime[0].length;
  const directions = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ];
  const visited = Array.from({ length: m }, () => new Array(n).fill(false));
  const minHeap = new MinPriorityQueue(({ time }) => time);

  minHeap.enqueue({ row: 0, col: 0, time: 0 });
  visited[0][0] = true;

  while (minHeap.size()) {
    const { row, col, time } = minHeap.dequeue();

    if (row === m - 1 && col === n - 1) return time;

    for (const [moveRow, moveCol] of directions) {
      const nextRow = row + moveRow;
      const nextCol = col + moveCol;

      if (nextRow < 0 || nextCol < 0 || nextRow >= m || nextCol >= n || visited[nextRow][nextCol]) continue;
      const nextTime = 1 + Math.max(time, moveTime[nextRow][nextCol]);

      minHeap.enqueue({ row: nextRow, col: nextCol, time: nextTime });
      visited[nextRow][nextCol] = true;
    }
  }

  return -1;
};