Easy C++ Dijkstra with conditions
Intuition\n Describe your first thoughts on how to solve this problem. \nIt seemed like a straightforward shortest path problem with some modification due to th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIt seemed like a straightforward shortest path problem with some modification due to the given condition: \n\n>  You can visit the cell `(row, col)` only when the time you visit it is **greater than or equal** to `grid[row][col]`.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nA simple dijkstra where the following conditions are kept in mind:\n\n> If the `value` of adjacent element is less than the distance required to reach it, then the distance will be exactly `distance[x][y] + 1`\n\n> Otherwise two cases:\n1. **The parity is same:** the distance will be exactly `grid[x][y] + 1` because you can visit the previous cell and come back but then the distance would be \n`(dis[x][y] + 1) + 1`\n\n2. **The parity is different:** the distance will be exactly `grid[x][y]` because you can just visit the previous cell and come back and then the distance would be \n`(dis[x][y] + 1)`\n\n# Complexity\n- Time complexity: $$O((M * N) * log(M * N) + (M * N))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(M*N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n// please upvote if you find it useful :)\nclass Solution {\npublic:\n    int minimumTime(vector<vector<int>>& grid) {\n        int n = grid.size();\n        int m = grid[0].size();\n        \n        // -1 condition\n        \n        if(grid[0][1] > 1 and grid[1][0] > 1){\n            return -1;\n        }\n        \n        // main code\n        vector<vector<int>> dis(n + 1, vector<int> (m + 1, 1e6));\n        \n        priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<>> q;\n        \n        q.push({0,{0,0}}); // dist, src_x, src_y\n        \n        dis[0][0] = 0;\n        \n        while(!q.empty()){\n            int d = q.top().first;\n            int x = q.top().second.first;\n            int y = q.top().second.second;\n            q.pop();\n            if (d > dis[x][y]) continue; // Skip if `d` is not updated to latest version!\n            \n            // move down\n            if(x + 1 < n){\n                if(dis[x + 1][y] > d + 1){\n                    \n                    if(grid[x + 1][y] <= d + 1){\n                        dis[x + 1][y] = d + 1;\n                    }\n                    else{\n                        dis[x + 1][y] = ((grid[x + 1][y] % 2) == (d % 2) ? (grid[x + 1][y] + 1) : grid[x + 1][y]);\n                    }\n                    q.push({dis[x + 1][y],{x + 1, y}});\n                    \n                }\n                \n            }\n            \n            // move up\n            if(x - 1 >= 0){\n                if(dis[x - 1][y] > d + 1){\n                    \n                    if(grid[x - 1][y] <= d + 1){\n                        dis[x - 1][y] = d + 1;\n                    }\n                    else dis[x - 1][y] = ((grid[x - 1][y] % 2) == (d % 2) ? (grid[x - 1][y] + 1) : grid[x - 1][y]);\n                    q.push({dis[x - 1][y], {x - 1, y}});\n                }\n                \n            }\n            \n            // move right\n            if(y + 1 < m){\n                if(dis[x][y + 1] > d + 1){\n                    \n                    if(grid[x][y + 1] <= d + 1){\n                        dis[x][y + 1] = d + 1;\n                    }\n                    else dis[x][y + 1] = (dis[x][y + 1], (grid[x][y + 1] % 2) == (d % 2) ? (grid[x][y + 1] + 1) : grid[x][y + 1]);\n                    q.push({dis[x][y + 1], {x, y + 1}});\n                }\n                \n            }\n            \n            // move left\n            if(y - 1 >= 0){\n                if(dis[x][y - 1] > d + 1){\n                    \n                    if(grid[x][y - 1] <= d + 1){\n                        dis[x][y - 1] = d + 1;\n                    }\n                    else dis[x][y - 1] = ((grid[x][y - 1] % 2) == (d % 2) ? (grid[x][y - 1] + 1) : grid[x][y - 1]);\n                    q.push({dis[x][y - 1],{x, y - 1}});\n                }\n                \n            }\n            \n            \n        }\n        \n        return dis[n - 1][m - 1];\n    }\n};\n```\n# Questions Asked:\n1. How does this work `if (d > dis[x][y]) continue;`?\n- Firstly it wasn\'t necessary here because any cell can be visited at most 4 times so the current cell `{x, y}` would have been pushed to the minHeap that many times. In the worst case, the cell will pop and process for its adjacent cells that can be atmost 4, each time it takes time to visit adjacent cells, there is up to 4 cells like current cell.\n\n- What if it was a graph question where a node may be connected to V other nodes, so in that case this line can be useful in avoiding visiting all V nodes as explained above.
['Shortest Path', 'C++']