Detailed Dry-Run Approach
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires us to navigate through a grid of rooms, each with a designated tim
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires us to navigate through a grid of rooms, each with a designated time that must pass before we can move into it.To solve this, the use of a graph traversal algorithm is necessary since the solution involves finding the shortest path in terms of time.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Declaration\n    - Create a priority queue(Min-Heap) to store rooms as we explore them, initialized with the starting room (0,0) at time 0 with a count of 0.\n    - Maintain a temp array to track the minimum time required to reach each room. temp[0][0] is initialised to zero since we start here and time taken to reach this is 0 seconds. Others can be initialised with a high value(here INT_MAX is taken).\n    \n- Path Exploration\n    - While the priority queue is not empty, pop the room currently with the minimum accumulated time.\n    - For each room, check its four possible neighbors (up, down, left, right).[for (i,j) the possible paths are:- (i+1,j),(i-1,j),(i,j+1),(i-j-1)]\n    - Calculate the waiting time to enter each neighbor based on the current time and the room\'s entry time(here 1 second or  seconds[flipping simultaneously]).\n    - If this new time is less than the previously recorded time for that neighbor, update the time and push the neighbor into the priority queue.\n    - While undergoing such transitions for path finding, if we encounter (n-1,m-1) we return the current time curr.\n    - After the whole min-heap is processed, we check if nothing has been returned, we return \u22121(disconnected component)\n\n# Example\n\ngrid=[[0,2],[1,4]]\n\n- Declaration\n    - We start at room (0,0) at time 0.\n    - The priority queue is initialized with pq={0,{0,0}}.\n    - The temp array is initialized as:- [[0,INT_MAX],[INT_MAX,INT_MAX]]\n    \n-   Path Exploration \n    - 1st iteration\n        - Pop the element from the queue: $curr=0$, $(x,y)=(0,0)$,$cnt=0$.\n        - Check if we\'ve reached the target (1,1).[False]\n        - Explore neighbors:-\n            - $Right(0,1)$:-\n                - New time calculation:$add=(cnt?2:1)=1$,      $wait=max(0,2)+1=3$.\n                - Since 3<INT_MAX, update $temp[0][1]$ $to$ $3$ and push to heap.\n                - temp=[[0,3],[INT_MAX,INT_MAX]]\n                - pq={3,{0,1,1}}\n            - $Down(1,0)$:-\n                - New time calculation:$add=(cnt?2:1)=1$,$wait=max(0,1)+1=2$\n                - Since 2<INT_MAX, update $temp[1][0]$ $to$ $2$ and push to heap.\n                - temp=[[0,3],[2,INT_MAX]]\n                - pq={{2,{1,0,1}},{3,{0,1,1}}}  \n            - $Up$ and $Left$ are out of bounds. \n    \n    - 2nd Interation\n        - Pop the element from the queue: $curr=2$,$(x,y)=(1,0)$,$cnt=1$.\n        - Check if we\'ve reached the target (1,1): [False]\n        - Explore neighbors:\n            - $Up(0,0)$:\n                - Already visited with temp[0][0]=0, so we skip.\n            - $Down(1,1)$:\n                - New time calculation:$add=(cnt?2:1)=2$,$wait=max(2,4)+2=6$.\n                - Since 5<INT_MAX, update $temp[1][1$] $to$ $5$ and push to heap.\n                - temp=[[0,3],[2,6]]\n                - pq={{3,{0,1,1}},{6,{1,1,0}}}\n                - $Left$ out of bounds.\n                - $Right(1,1)$ already computed.    \n\n    - 3rd Iteration\n        - Pop the element from the queue: $curr=3$, $(x,y)=(0,1)$,$cnt=1$.\n        - Check if we\'ve reached the target (1,1): [False]\n        - Explore neighbors:\n            - $Up$: Out of bounds, so we skip.\n            - $Down(1,1)$:\n                    - New time calculation:$add=(cnt?2:1)=2$,wait=max(3,4)+2=6.\n                    - Since 6>=temp[1][1], we skip.\n            - temp=[[0,3],[2,6]]\n            - pq={{6,{1,1,0}}}\n            - $Left(0,0)$:Already computed\n            - $Right(0,2)$:Out of bounds\n    \n    - 4th Iteration\n        - Pop the element from the queue: $curr=6$,$(x,y)=(1,1)$.\n        - Check if we\'ve reached the target (1,1):[True]\n        - Return:- $curr=6$.\n\n\n\n# Complexity\n- Time complexity:-$O(n*m*log(n*m))$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:-$O(n*m)+O(n*m)$ One for storing the $temp$ array and other for the $priority$ $queue$(Worst Case)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minTimeToReach(vector<vector<int>>&grid) {\n        int n=grid.size(),m=grid[0].size();\n        vector<pair<int,int>>dir={{0,1},{1,0},{0,-1},{-1,0}};\n        \n        //int cnt=0;\n        priority_queue<pair<int,vector<int>>,vector<pair<int,vector<int>>>,greater<pair<int,vector<int>>>>pq;\n        pq.push({0,{0,0,0}});\n\n        vector<vector<int>>temp(n,vector<int>(m,INT_MAX));\n        temp[0][0]=0;\n        while(!pq.empty())\n            {\n                auto it=pq.top();\n                pq.pop();\n                int curr=it.first;\n                int x=it.second[0],y=it.second[1],cnt=it.second[2];\n                if(x==n-1 && y==m-1)\n                    return curr;\n                for(int i=0;i<4;++i)\n                    {\n                        int nx=x+dir[i].first;\n                        int ny=y+dir[i].second;\n                        if(nx>=0 && nx<n && ny>=0 && ny<m)\n                        {\n                            int add=(cnt)?2:1;\n                            int wait=max(curr,grid[nx][ny])+add;\n                            if(wait<temp[nx][ny])\n                            {\n                                temp[nx][ny]=wait;\n                                pq.push({wait,{nx,ny,1-cnt}});\n                            }\n                        }\n                    }\n            }\n    return -1;\n    }\n};\n```
['Graph', 'Heap (Priority Queue)', 'Shortest Path', 'C++']