2025-05-07 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's May LeetCoding Challenge with cpp.

May LeetCoding Challenge 7

Description

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.

  • 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

Solution

class Solution {
  using pi = pair<int, int>;
  const int MOVES[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
public:
  int minTimeToReach(vector<vector<int>>& moveTime) {
    int rows = moveTime.size();
    int cols = moveTime.front().size();
    int target = rows * cols - 1;

    priority_queue<pi, vector<pi>, greater<>> pq;
    pq.push({0, 0});
    set<int> visited;
    while(pq.size()) {
      auto [time, position] = pq.top();
      pq.pop();
      if(position == target) return time;
      if(visited.count(position)) continue;
      visited.insert(position);

      int row = position / cols;
      int col = position % cols;
      for(int m = 0; m < 4; ++m) {
        int newRow = row + MOVES[m][0];
        int newCol = col + MOVES[m][1];
        int newPos = newRow * cols + newCol;
        if(newCol < 0 || newRow < 0 || newCol >= cols || newRow >= rows) continue;
        if(visited.count(newPos)) continue;
        pq.push({max(time + 1, moveTime[newRow][newCol] + 1), newPos});
      }
    }
    return -1;
  }
};

// Accepted
// 743/743 cases passed (44 ms)
// Your runtime beats 16.42 % of cpp submissions
// Your memory usage beats 28.64 % of cpp submissions (31 MB)
Algorithm