Find Minimum Time to Reach Last Room II

Leetcode has become stale or what?!

Basically just the last question, except now you have to keep track of the time taken to reach the next element as it now alternates between 1 & 2.

code

class Room {
public:
    int x;
    int y;
    int minTime;
    int move;
    Room(int x, int y, int minTime, int move): x(x), y(y), minTime(minTime), move(move) {};

    bool operator< (const Room& rhs) const {
        return minTime > rhs.minTime;
    }
};

class Solution {
public:
    int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int minTimeToReach(vector<vector<int>>& moveTime) {
        int n = moveTime.size(), m = moveTime[0].size();
        vector<vector<int>> d(n, vector<int>(m, 0));

        priority_queue<Room, vector<Room>> pq;
        pq.push(Room(0, 0, 0, 1));
        moveTime[0][0] = -1;

        while (!pq.empty()) {
            Room curr = pq.top();
            pq.pop();

            if (curr.x == n - 1 && curr.y == m - 1) break;

            for (int i = 0; i < 4; ++i) {
                int new_x = curr.x + directions[i][1];
                int new_y = curr.y + directions[i][0];

                if (new_x >= 0 && new_x < m && new_y >= 0 && new_y < n && moveTime[new_y][new_x] != -1) {
                    int maxTime = max(curr.minTime, moveTime[new_y][new_x]) + curr.move;
                    pq.push(Room(new_x, new_y, maxTime, (curr.move%2)+1));
                    d[new_y][new_x] = maxTime;
                    moveTime[new_y][new_x] = -1;
                }
            }
        }

        return d[n-1][m-1];
    }
};

complexity

• Time: O(mn * log(mn))
• Space: O(mn)