C++ Modified Dijkstra | Detailed Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \nWe are asked to move in adjacent cell every second.\nBut what if the unvisited cell\'s 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe are asked to move in adjacent cell every second.\nBut what if the unvisited cell\'s time is much more greater than current time passed?\nHere, we will need to iterate on the peviously visited cells so that the time is passed. But doing this will lead to TLE.\nSo, we need to keep a track of at what minimum time the cell can be visited after re-iterating on the visited cells.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- If`grid[0][1]`and`grid[1][0]`are greater than 1, then we cannot move anywhere from the first cell. So answer will be`-1`.\n- If`time passed + 1 sec`is greater than or equal to`grid[i][j]`, then the cell will unlock at the same instance.\n- Else, we will need to waste some time visiting the already visited cells so that the time is passed and the cell will unlock.\nIf we are standing at a cell and no matter whichever path is chosed to visit the already visited cells, it will always take`even`amount of time to go and come back to the current cell.\nSo, if the time passed is even,\n    - If`grid[i][j]`is odd, then cell`{i, j}`will unlock at`grid[i][j]`time because revisiting the visited cells and coming back will take even amount of time no matter whichever path is traversed and then +1 second to go to locked cell.\n    - If`grid[i][j]`is even, then cell`{i, j}`will unlock at`grid[i][j] + 1`time.\n- If time passed is odd,\n    - If`grid[i][j]`is even, then cell`{i, j}`will unlock at`grid[i][j]`time because revisiting the visited cells and coming back will take even amount of time no matter whichever path is traversed and then +1 second to go to locked cell.  \n    - If`grid[i][j]`is odd, then cell`{i, j}`will unlock at`grid[i][j] + 1`time.\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).\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\nprivate:\n    vector<int> dr = {0, +1, 0, -1};\n    vector<int> dc = {+1, 0, -1, 0};\n\npublic:\n    bool isValid(int row, int col, int n, int m) {\n        return (row >= 0 && row < n && col >= 0 && col < m);\n    }\n\n    int minimumTime(vector<vector<int>>& grid) {\n        int n = grid.size(), m = grid[0].size();\n\n        // We can\'t iterate anywhere except the first cell.\n        if(grid[0][1] > 1 && grid[1][0] > 1) {\n            return -1;\n        }\n\n        vector<vector<int>> vis(n, vector<int>(m, -1));\n        set<pair<int, pair<int, int>>> st;\n        // {time, {row, col}}.\n        st.insert({0, {0, 0}});\n        vis[0][0] = 0;\n\n        while(st.size() != 0) {\n            auto it = *(st.begin());\n            int time = it.first;\n            int x = it.second.first;\n            int y = it.second.second;\n            st.erase(it);\n\n            for(int i = 0; i < 4; ++i) {\n                int newX = x + dr[i];\n                int newY = y + dc[i];\n                if(isValid(newX, newY, n, m) && vis[newX][newY] == -1) {\n                    // No need to waste time as cell is already unlocked.\n                    if(time + 1 >= grid[newX][newY]) {\n                        vis[newX][newY] = time + 1;\n                        st.insert({time + 1, {newX, newY}});\n                    }\n                    // Need to waste time.\n                    else {\n                        if(time % 2 == 0) {\n                            if(grid[newX][newY] % 2 == 1) {\n                                vis[newX][newY] = grid[newX][newY];\n                                st.insert({grid[newX][newY], {newX, newY}});\n                            }   \n                            else {\n                                vis[newX][newY] = grid[newX][newY] + 1;\n                                st.insert({grid[newX][newY] + 1, {newX, newY}});\n                            }\n                        }\n                        else {\n                            if(grid[newX][newY] % 2 == 0) {\n                                vis[newX][newY] = grid[newX][newY];\n                                st.insert({grid[newX][newY], {newX, newY}});\n                            }   \n                            else {\n                                vis[newX][newY] = grid[newX][newY] + 1;\n                                st.insert({grid[newX][newY] + 1, {newX, newY}});\n                            }\n                        }\n                    }\n                }\n            }\n        }\n\n        return vis[n - 1][m - 1];\n    }\n};\n```
['Graph', 'Matrix', 'Ordered Set', 'Shortest Path']