Beat 95% users || C++ || Easy to understand || Detailed Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves traversing a grid, starting from the top-left corner to the bottom
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves traversing a grid, starting from the top-left corner to the bottom-right corner, with each cell having a time value. The movement from one cell to another can only happen under certain conditions based on the time, and some cells may require a wait to become accessible. The goal is to find the minimum time required to reach the destination, considering these constraints\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can approach this problem using a modified Dijkstra\u2019s algorithm with a priority queue. Each state will store the current time and position in the grid. At each step, we explore the neighboring cells, calculate the required time to move to that cell, and push the new state into the priority queue. The **wait** condition determines whether we need to delay moving to a cell. If a cell is visited for the first time, we proceed to explore its neighbors. The algorithm will stop once we reach the destination.\n\n**Steps:**\n1. Start from the top-left cell with time 0.\n2. Use a priority queue to always process the cell with the least time.\n3. For each cell, check its four neighbors. For each valid neighbor, calculate the time to move to it (considering the wait time).\n4. Push the new state (time and position) into the priority queue.\n5. Stop when the bottom-right cell is reached or if no valid path exists.\n# Complexity\n- Time complexity: $$O(m*n*log(m*n))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nWe process each cell at most once, and for each cell, we perform a constant amount of work to check its neighbors and update the priority queue.\n- Space complexity: $$O(m*n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nWe store the visited cells and the priority queue, both of which have a size proportional to the number of cells in the grid.\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minimumTime(vector<vector<int>>& grid) {\n        if(min(grid[0][1],grid[1][0])>1) return -1;\n        priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq;\n        pq.push({0,{0,0}}); //time,row,column\n        int m = grid.size();\n        int n = grid[0].size();\n        vector<vector<int>> visit(m,vector<int>(n,0));\n        while(!pq.empty()){\n            auto it = pq.top();\n            pq.pop();\n            int t = it.first;\n            int r = it.second.first;\n            int c = it.second.second;\n            if(r==m-1 && c==n-1) return t;\n            int row[] = {0,-1,0,1};\n            int col[] = {-1,0,1,0};\n            for(int i=0;i<4;i++){\n                int nr = r+row[i];\n                int nc = c+col[i];\n                if(nr<0 || nc<0 || nr==m || nc==n || visit[nr][nc]==1){\n                    continue;\n                }\n                int wait = 0;\n                if(abs(grid[nr][nc]-t)%2==0){\n                    wait = 1;\n                }\n                int newtime = max(grid[nr][nc]+wait,t+1);\n                pq.push({newtime,{nr,nc}});\n                visit[nr][nc] = 1;\n            }\n        }\n        return 0;\n    }\n    \n};\n```
['Breadth-First Search', 'Heap (Priority Queue)', 'Matrix', 'Shortest Path', 'C++']