[C++] Djikstra's + Easy Hack for deciding between 1 or 2 (Even vs Odd Diagonal)
Intuition\n Describe your first thoughts on how to solve this problem. \nSame approach as 3341. but instead we have to account for either adding 1 or 2 dependin
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSame approach as [3341.](https://leetcode.com/problems/find-minimum-time-to-reach-last-room-i/description/) but instead we have to account for either adding 1 or 2 depending on the room. Note that traveling into rooms on odd diagonals will always require a time of $2$ seconds while rooms on the even diagonals always require $1$ second. This can be quickly identified by the boolean value `evenCol = (newCol+newRow)%2`, where `newCol` and `newRow` are the col and row index of the room we\'re trying to move into.\n\n# Approach\nModified Djikstra\'s\n# Complexity\n- Time complexity:\n$O((V + E) \\log V) =  O((mn+4mn)\\log(mn))=O(mn\\cdot\\log (mn))$\n- Space complexity:\n$O(V) = O(mn)$\n# Code\n```cpp []\nclass Solution {\nconst vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};\npublic:\n    int minTimeToReach(vector<vector<int>>& moveTime) {\n        //Djikstra\n        int n = moveTime.size();\n        int m = moveTime[0].size();\n        //distance from 0,0 to i,j\n        vector<vector<int>> dist(n, vector<int>(m, INT_MAX));\n        dist[0][0] = 0;\n        \n        //Priority Queue to maintain closest room we have not visited yet\n        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;\n        pq.push({0, 0, 0});\n        while (!pq.empty()) {\n            auto [currentDist, row, col] = pq.top();\n            pq.pop();\n            \n            if (row == n - 1 && col == m - 1) {\n                return currentDist;  \n            }\n            \n            for (const auto& [dx, dy] : directions) {\n                int newRow = row + dx;\n                int newCol = col + dy;\n                \n                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m) {\n                    int travelTime = 2-(newRow+newCol)%2; // =(newRow+newCol)%2? 1:2;\n                    \n                    int newDist = max(currentDist, moveTime[newRow][newCol])+travelTime;\n                    \n                    if (newDist < dist[newRow][newCol]) {\n                        dist[newRow][newCol] = newDist;\n                        pq.push({newDist, newRow, newCol});\n                    }\n                }\n            }\n        }    \n        return dist[n-1][m-1];\n    }\n};\n```
['C++']