100% Beats Baby Solution
Intuition\nThe problem involves finding the minimum time required to traverse a grid with specific constraints. The intuition is to treat this as a pathfinding 
# Intuition\nThe problem involves finding the minimum time required to traverse a grid with specific constraints. The intuition is to treat this as a pathfinding problem where each cell has a cost, influenced by its value and traversal rules. Using Dijkstra\'s algorithm or a priority queue allows us to efficiently explore the grid and minimize the traversal cost.\n#\n-----\n![DALL\xB7E 2024-11-19 06.48.02 - Create a cute and colorful illustration of an upvote icon with a playful design. The upvote arrow is stylized with a smiling face and surrounded by sp.webp](https://assets.leetcode.com/users/images/7bd70717-d8d9-49cb-92e2-36dfe3b6a659_1732847146.4049764.webp)\n\n\n# Approach\n1. **Edge Case Handling**: Check if the grid\'s first step is infeasible (`grid[0][1] > 1` and `grid[1][0] > 1`), as no valid path can exist in such cases.\n2. **Initialization**:\n   - Use a priority queue to always process the smallest cost first.\n   - Maintain a `distance` matrix initialized to `INT_MAX` to track the minimum cost to reach each cell.\n3. **Traversal**:\n   - Start at the top-left corner with cost `0`.\n   - Explore all four possible directions (up, down, left, right).\n   - Calculate the additional time cost required to reach the next cell based on its value and the current time (`v`).\n   - Push the new state into the priority queue if a better time is found.\n4. **Termination**: The process terminates when the bottom-right cell is dequeued from the priority queue, yielding the minimum cost. If unreachable, return `-1`.\n\n# Complexity\n- **Time Complexity**:  \n  $$O(m \\cdot n \\cdot \\log(m \\cdot n))$$  \n  where \\(m\\) and \\(n\\) are the grid\'s dimensions. Each cell is processed once, and each operation in the priority queue takes \\(O(\\log(m \\cdot n))\\).\n\n- **Space Complexity**:  \n  $$O(m \\cdot n)$$  \n  for the `distance` matrix and priority queue.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minimumTime(vector<vector<int>>& grid) {\n        if (grid[0][1] > 1 && grid[1][0] > 1)\n            return -1; // edge case\n        int m = grid.size(), n = grid[0].size();\n        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,\n                       greater<>>\n            pq;\n        vector<vector<int>> d(m, vector<int>(n, INT_MAX));\n        pq.push({0, 0, 0});\n        d[0][0] = 0;\n        while (!pq.empty()) {\n            auto [v, i, j] = pq.top();\n            pq.pop();\n            if (i == m - 1 && j == n - 1)\n                return v;\n            int dir[5] = {-1, 0, 1, 0, -1};\n            for (int k = 0; k < 4; ++k) {\n                int ii = i + dir[k], jj = j + dir[k + 1];\n                if (ii >= 0 && ii < m && jj >= 0 && jj < n) {\n                    int diff = grid[ii][jj] - v;\n                    if (diff < 0)\n                        diff = 0;\n                    else if (diff & 1)\n                        diff = diff / 2 * 2;\n                    int vv = v + 1 + diff;\n                    if (d[ii][jj] > vv) {\n                        d[ii][jj] = vv;\n                        pq.push({vv, ii, jj});\n                    }\n                }\n            }\n        }\n        return -1;\n    }\n};\nvoid FastIO() {\n    ios_base::sync_with_stdio(0);\n    cin.tie(0);\n    // cout.tie(0);\n}\n```
['C++']