3341: Find-Minimum-Time-to-Reach-Last-Room-I
Medium

This question is just a simple djikstra’s algorithm, where you place the unseen rooms into a priority_queue sorted by the min_time required to reach that room.

Then, each “edge” is simply just the larger element between moveTime[new_x][new_y] + 1 and the current Room.min_time + 1.

Code:

class Room {
public:
    int x;
    int y;
    int min_time;
};

class Solution {
public:
    bool CompareRoom(Room r1, Room r2) {
        return r1.min_time < r2.min_time;
    }
    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));

        auto cmp = [](const Room& a, const Room& b) { return a.min_time > b.min_time; };
        priority_queue<Room, vector<Room>, decltype(cmp)> pq(cmp);
        pq.push(Room(0, 0, 0));
        moveTime[0][0] = -1;

        while(!pq.empty()) {
            Room top = pq.top();
            pq.pop();
            
            if (top.x == n - 1 && top.y == m - 1) break;
            
            for (int i = 0; i < 4; ++i) {
                int new_x = top.x + directions[i][1];
                int new_y = top.y + directions[i][0];

                if (new_x >= 0 && new_x < m && new_y >= 0 && new_y < n && moveTime[new_y][new_x] != -1) {
                    int max_time = max(top.min_time, moveTime[new_y][new_x])+1;
                    pq.push(Room(new_x, new_y, max_time));
                    d[new_y][new_x] = max_time;
                    moveTime[new_y][new_x] = -1;
                }
            }
        }

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

Complexity:

Learnings:

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;
    }
};