Dijkstra's Algorithm||87ms Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nIt\'s again a question on shortest path.\nSo, Dijkstra\'s Algorithm is applied again.\n
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIt\'s again a question on shortest path.\nSo, Dijkstra\'s Algorithm is applied again.\nThe solution is almost the same in solving [3341. Find Minimum Time to Reach Last Room I](https://leetcode.com/problems/find-minimum-time-to-reach-last-room-i/solutions/6000622/dijkstra-shortest-path18ms-beats-100/). Instead of waiting til the time comes, just make a back and forth movement when necessary, the number of such steps can be any multiple of 2.\n\nPython code is made.\nA* search solution is added.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. The only edge case is when `grid[1][0]>1 && grid[0][1]>1`, just return -1.\n2. Use matrix convention $n \\times m$ matrix `grid`\n3. Set min heap `pq` to hold the info tuple `(time, i, j)`; this part  can be slightly modified for the speed.\n4.  The distance matrix is 2d array `time`; this part can be modified.\n4. Push info tuple at (0, 0) with time=0 to pq; set `time[0][0]=0`\n5. As long as `pq` is not empty, proceed the BFS over `pq`\n6. Get the info tuple from the top, say `[t, i, j] = pq.top()` then pop\n7. If reaching the destination return `t`\n8. Traverse all four directions, check the adjacent cell `isOutside(r, s, n, m)`, if yes skip it\n9. Compute minimum time to reach (r, s)\n```\nint w=((grid[r][s]-t)&1)?0:1;\nint nextTime = max(t+1, grid[r][s]+w);// backward if neccessary\n```\n11. update if this path having quicker time\n```\nif (nextTime < time[r][s]) {\n    time[r][s] = nextTime;\n    pq.emplace(nextTime, r, s);\n}\n```\n12. End of the loop, put `return -1;` that will never reach.\n13. Version 2 & Version 3 are so made that 2D arrays are converted into 1D ones, & possibly use C-arrays. \n14. The 3rd C++ version `pq` holds the 64-bit int `((uint64_t)time<<32)+idx(i, j))` which is a C-array.\n15. The pop, push in 1st version is replaced by `pop_heap, push_heap` in the 3rd version.\n# Why no visited array?\nDijkstra\'s Algorithm is in fact a Greedy Algorithm finding the shortest path with ****non-negative weights****. In the codes `if (nextTime < time[r][s]){...}` eliminates the possiblity for revisiting the cell `(r,s)`. By several times of praticing Dijsktra\'s Algorithm, it makes me to figure out this fact.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(nm \\log(nm))$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(nm)$$\n# Code||C++ v1 131ms Beats 96.32%||C++ v3 87ms Beats 100%\n\n```cpp [C++ v1]\nusing info = tuple<int, short, short>; // (time, i, j)\nconst static int d[5] = {0, 1, 0, -1, 0};\nclass Solution {\npublic:\n    inline static bool isOutside(short i, short j, short n, short m) {\n        return i < 0 || i >= n || j < 0 || j >= m;\n    }\n\n    int minimumTime(vector<vector<int>>& grid) {\n        if (grid[1][0]>1 && grid[0][1]>1)  return -1;// edge case\n    \n        short n = grid.size(), m = grid[0].size();\n        vector<vector<int>> time(n, vector<int>(m, INT_MAX));\n        priority_queue<info, vector<info>, greater<info>> pq;\n\n        // Start at (0, 0) with time=0 \n        pq.emplace(0, 0, 0);\n        time[0][0] = 0;\n        while (!pq.empty()) {\n            auto [t, i, j] = pq.top();\n            pq.pop();\n        //    cout<<" t="<<int(t)<<" i="<<int(i)<<" j="<<int(j)<<endl;\n            // reach the destination\n            if (i == n - 1 && j == m - 1)\n                return t;\n\n            // Traverse all four directions\n            for (int a = 0; a < 4; a++) {\n                int r = i + d[a], s = j + d[a + 1];\n                if (isOutside(r, s, n, m)) continue;\n\n                // minimum time to reach (r, s)\n                int w=((grid[r][s]-t)&1)?0:1;\n                int nextTime = max(t+1, grid[r][s]+w); // backward if neccessary\n\n                // update if this path having quicker time\n                if (nextTime < time[r][s]) {\n                    time[r][s] = nextTime;\n                    pq.emplace(nextTime, r, s);\n                }\n            }\n        }\n\n        return -1; // never reach\n    }\n};\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n```cpp [C++ v3]\nusing info = pair<int, int>; // (time, i*m+j)\nconst static int d[5] = {0, 1, 0, -1, 0};\nclass Solution {\npublic:\n    inline static bool isOutside(int i, int j, int n, int m) {\n        return i < 0 || i >= n || j < 0 || j >= m;\n    }\n    inline static int idx(int i, int j, int m) { return i * m + j; }\n\n    int minimumTime(vector<vector<int>>& grid) {\n        if (grid[1][0] > 1 && grid[0][1] > 1)\n            return -1; // edge case\n\n        const int n = grid.size(), m = grid[0].size(), N = 100000;\n        int time[N];\n        fill(time, time + n * m, INT_MAX);\n        uint64_t pq[N];\n        int back = 0;\n\n        // Start at (0, 0) with time=0\n        pq[back++] = 0;\n        time[0] = 0;\n        while (back > 0) {\n            pop_heap(pq, pq + back, greater<>{});\n            auto tij = pq[--back];\n            int t = tij >> 32, ij = tij & ((1 << 30) - 1), i = ij / m,\n                j = ij - i * m;\n\n            //    cout<<" t="<<int(t)<<" i="<<int(i)<<" j="<<int(j)<<endl;\n            // reach the destination\n            if (i == n - 1 && j == m - 1)\n                return t;\n\n            // Traverse all four directions\n            for (int a = 0; a < 4; a++) {\n                int r = i + d[a], s = j + d[a + 1];\n                if (isOutside(r, s, n, m))\n                    continue;\n\n                // minimum time to reach (r, s)\n                int w = ((grid[r][s] - t) & 1) ? 0 : 1;\n                int nextTime =\n                    max(t + 1, grid[r][s] + w); // backward if neccessary\n\n                // update if this path having quicker time\n                int rs=idx(r, s, m);\n                if (nextTime < time[rs]) {\n                    time[rs] = nextTime;\n                    pq[back++] = ((uint64_t)nextTime << 32) + rs;\n                    push_heap(pq, pq + back, greater<>{});\n                }\n            }\n        }\n\n        return -1; // never reach\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# Dijkstra\'s algorithm is suitible to find the shortest path in a weighted Graph\n[Please turn on English subtitles if necessary. 1631  Path With Minimum Effort]\n[https://youtu.be/IkpRzCICL_g?si=joY6antLDgu2RHpB](https://youtu.be/IkpRzCICL_g?si=joY6antLDgu2RHpB)\nMany questions can be solved by using variants of Dijkstra\'s algorithm.\n[1631. Path With Minimum Effort](https://leetcode.com/problems/path-with-minimum-effort/solutions/4049711/c-dijkstra-s-algorithm-vs-dfs-binary-search-vs-union-find-pseudo-metric-91-ms-beats-98-93/)\n[2699. Modify Graph Edge Weights](https://leetcode.com/problems/modify-graph-edge-weights/solutions/5709135/dijkstras-algo-finds-min-distance-by-adding-wildcard-edges477ms-beats-9485/)\n[2290. Minimum Obstacle Removal to Reach Corner](https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/solutions/6090250/dijkstra-algorithm-with-weights-same-as-grid-vs-bfs-over-circular-deque-beats-100/)\n[3341. Find Minimum Time to Reach Last Room I](https://leetcode.com/problems/find-minimum-time-to-reach-last-room-i/solutions/6000622/dijkstra-shortest-path18ms-beats-100/)\n[2699. Modify Graph Edge Weights](https://leetcode.com/problems/modify-graph-edge-weights/solutions/5709135/dijkstras-algo-finds-min-distance-by-adding-wildcard-edges477ms-beats-9485/)<--Hardest one ever solved\n# Python code\n```\nclass Solution:\n    def minimumTime(self, grid: List[List[int]]) -> int:\n        if grid[1][0] > 1 and grid[0][1] > 1:\n            return -1\n        R, C = len(grid), len(grid[0])\n\n        def isOutside(i, j):\n            return i < 0 or i >= R or j < 0 or j >= C\n\n        def idx(i, j):\n            return i * C + j\n\n        N = R * C\n        time = [2**31] * N\n        pq = [0]\n\n        time[0] = 0\n        while len(pq):\n            tij = heappop(pq)\n            t, ij = tij >> 32, tij & ((1 << 30) - 1)\n            i, j = divmod(ij, C)\n            if i == R - 1 and j == C - 1:\n                return t\n\n            for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:\n                r, s = i + di, j + dj\n                if isOutside(r, s):\n                    continue\n\n                w = 0 if (grid[r][s] - t) & 1 else 1\n                nextTime = max(t + 1, grid[r][s] + w)\n\n                rs = idx(r, s)\n                if nextTime < time[rs]:\n                    time[rs] = nextTime\n                    heappush(pq, (nextTime << 32) + rs)\n        return -1\n\n```\n# A* search \n```\nconst static int d[5] = {0, 1, 0, -1, 0};\nclass Solution {\npublic:\n    inline static bool isOutside(int i, int j, int n, int m) {\n        return i < 0 || i >= n || j < 0 || j >= m;\n    }\n    inline static int idx(int i, int j, int m) { return i * m + j; }\n    // Use Manhattan distance as heuristic function\n    inline static int64_t h(int i, int j, int n, int m) {\n        return n + m - 2 - i - j;\n    }\n\n    int minimumTime(vector<vector<int>>& grid) {\n        if (grid[1][0] > 1 && grid[0][1] > 1)\n            return -1; // edge case\n\n        const int n = grid.size(), m = grid[0].size(), N = 100000;\n        int time[N];\n        fill(time, time + n * m, INT_MAX);\n        uint64_t pq[N];\n        int back = 0;\n\n        // Start at (0, 0) with f=0+h, note f<<32\n        pq[back++] = h(0, 0, n, m)<<32;\n        time[0] = 0;\n        while (back > 0) {\n            pop_heap(pq, pq + back, greater<>{});\n            auto fij = pq[--back];\n            int f = fij >> 32, ij = fij & ((1 << 30) - 1), i = ij / m,\n                j = ij - i * m;\n            int heur=h(i, j, n, m), t=f-heur;\n            //    cout<<" t="<<int(t)<<" i="<<int(i)<<" j="<<int(j)<<endl;\n            // reach the destination\n            if (heur==0)\n                return t;\n\n            // Traverse all four directions\n            for (int a = 0; a < 4; a++) {\n                int r = i + d[a], s = j + d[a + 1];\n                if (isOutside(r, s, n, m) || time[idx(r, s, m)] != INT_MAX)\n                    continue;\n\n                // minimum time to reach (r, s)\n                int w = ((grid[r][s] - t) & 1) ? 0 : 1;\n                int nextTime =\n                    max(t + 1, grid[r][s] + w); // backward if neccessary\n\n                // update if this path having quicker time\n                int rs = idx(r, s, m);\n                if (nextTime < time[rs]) {\n                    time[rs] = nextTime;\n                    pq[back++] = ((h(r, s, n, m) + nextTime) << 32) + rs;\n                    push_heap(pq, pq + back, greater<>{});\n                }\n            }\n        }\n\n        return -1; // never reach\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n
['Array', 'Bit Manipulation', 'Breadth-First Search', 'Graph', 'Heap (Priority Queue)', 'Matrix', 'Shortest Path', 'C++', 'Python3']