[Python/C++] clean Dijkstra's algorithm solution with explanation
Explaination\n\nThis problem can be solved using the Dijkstra\'s algorithm with a small variation.\n\nFirstly, note that we can always reach the bottom-right ce
**Explaination**\n\nThis problem can be solved using the Dijkstra\'s algorithm with a small variation.\n\nFirstly, note that we can always reach the bottom-right cell of the matrix if we can move to at least one adjacent cell (i.e. `grid[0][1]` or `grid[1][0]`). After that, we can simply move back and forth to spend time as needed.\n\nIt\'s also worth noting that we may not always be able to move to an adjacent cell immediately. For example, in Example 1, we have to step back to cell (1,1) before moving to cell (1,3) because we must move every second.\n\nSince it takes an even number of seconds to "stand still" when moving back and forth, we need to wait for an extra second if we want to move after an odd number of seconds\n\nAfter accounting for these factors, we can use the standard Dijkstra\'s algorithm to find the answer.\n\n<br/>\n\n**Complexity**\n\nTime complexity: `O(MNlog(MN))`\nSpace complexity: `O(MN)`\n\n<br/>\n\n**Python**\n```Python\nclass Solution:\n    def minimumTime(self, grid: List[List[int]]) -> int:\n        m, n = len(grid), len(grid[0])\n        if grid[0][1] > 1 and grid[1][0] > 1:\n            return -1\n        visited = [[False] * n for _ in range(m)]\n        heap = [(0, 0, 0)] # (t, r, c)\n        while heap:\n            t, r, c = heapq.heappop(heap)\n            if r == m - 1 and c == n - 1:\n                return t\n            if visited[r][c]:\n                continue\n            visited[r][c] = True\n            for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):\n                nr, nc = r + dr, c + dc\n                if nr < 0 or nr >= m or nc < 0 or nc >= n or visited[nr][nc]:\n                    continue\n                wait = (grid[nr][nc] - t) % 2 == 0\n                nt = max(grid[nr][nc] + wait, t + 1)\n                heapq.heappush(heap, (nt, nr, nc))\n        return -1\n```\n\n<br/>\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int minimumTime(vector<vector<int>>& grid) {\n        int m = grid.size(), n = grid[0].size();\n        if (grid[0][1] > 1 && grid[1][0] > 1) {\n            return -1;\n        }\n        vector<vector<int>> directions{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n        vector<vector<bool>> visited(m, vector<bool>(n, false));\n        priority_queue<vector<int>, vector<vector<int>>, greater<>> pq;\n        pq.push({0, 0, 0}); // (t, r, c)\n        while (!pq.empty()) {\n            auto cur = pq.top();\n            int t = cur[0], r = cur[1], c = cur[2];\n            pq.pop();\n            if (r == m - 1 && c == n - 1) {\n                return t;\n            }\n            if (visited[r][c]) {\n                continue;\n            }\n            visited[r][c] = true;\n            for (const auto& dir : directions) {\n                int nr = r + dir[0], nc = c + dir[1];\n                if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc]) {\n                    continue;\n                }\n                bool wait = (grid[nr][nc] - t) % 2 == 0;\n                int nt = max(grid[nr][nc] + wait, t + 1);\n                pq.push({nt, nr, nc});\n            }\n        }\n        return -1;\n    }\n};\n```
['C++', 'Python3']