2025-05-08 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

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

May LeetCoding Challenge 8

Description

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 and two seconds for the next, alternating between the two.

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

Explanation:

The minimum time required is 7 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 two seconds.

Example 2:

Input: moveTime = [[0,0,0,0],[0,0,0,0]]

Output: 6

Explanation:

The minimum time required is 6 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 two seconds.
  • At time t == 3, move from room (1, 1) to room (1, 2) in one second.
  • At time t == 4, move from room (1, 2) to room (1, 3) in two seconds.

Example 3:

Input: moveTime = [[0,1],[1,2]]

Output: 4

 

Constraints:

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

Solution

inline constexpr int nextTime(int t) {
  return t % 3 ? t + 2 : t + 1;
}
class Solution {  
  using pi = pair<int, int>;
  const int MASK = (1 << 30) - 1;
  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, 1 << 30});
    set<int> visited;
    while(pq.size()) {
      auto [time, state] = pq.top();
      int position = state & MASK;
      pq.pop();
      if(position == target) return time;
      if(visited.count(position)) continue;
      visited.insert(position);

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

// Accepted
// 717/717 cases passed (1356 ms)
// Your runtime beats 11.81 % of cpp submissions
// Your memory usage beats 38.93 % of cpp submissions (146.5 MB)
Algorithm