Find Minimum Time to Reach Last Room I

Leetcode Problem:

• Find Minimum Time to Reach Last Room I

Summary

• Minimum Time to Reach the Room (Dungeon Problem)

Approach

• Priority Queue with Depth-First Search (DFS) to find the shortest path in a grid of rooms with different move times.

Complexity

• O(R*C*log(R*C)) due to the use of a priority queue, where R is the number of rows and C is the number of columns in the grid.

Explanation

• The solution uses a priority queue to keep track of the rooms to visit, sorted by their move times
• It also uses a DFS to explore the grid, starting from the top-left room
• The priority queue is updated after each room visit to reflect the new move times
• The algorithm returns the minimum time to reach the bottom-right room.

Solution Code:

struct _pair{
    int r;
    int c;
    int time;
};

struct _heap{
    _pair arr[2501];
    int size;
    _heap(){
        size = 1;
    }
    void push(_pair a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && arr[idx/2].time > arr[idx].time){
            _pair t= arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = t;
            idx /= 2;
        }
    }
    _pair pop(){
        _pair ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if(j >= size) break;
            if((j+1) < size && arr[j].time > arr[j+1].time){
                j++;
            }
            if(arr[i].time > arr[j].time){
                _pair t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else{
                break;
            }
        }

        return ret;
    }
    bool empty(){
        return size == 1;
    }
};


class Solution {
public:
    _heap h;
    bool visited[51][51] = {0};
    int minTimeToReach(vector>& moveTime) {
        int R = moveTime.size();
        int C = moveTime[0].size();

        h.push({0,0,0});
        visited[0][0] = true;
        int dy[] = {1, 0, -1, 0};
        int dx[] = {0, 1, 0, -1};
        while(!h.empty()){
            _pair p = h.pop();
            if(p.r == R-1 && p.c == C-1){
                return p.time;
            }
            for(int i = 0 ; i < 4; i++){
                int nr = p.r + dy[i];
                int nc = p.c + dx[i];
                if(nr < 0 || nr >= R || nc < 0 || nc >= C || visited[nr][nc]){
                    continue;
                }
                visited[nr][nc] = true;
                int ntime = max(p.time, moveTime[nr][nc]) + 1;
                h.push({nr, nc, ntime});
            }
        }
        return -1;
    }
};