Modified Dijkshtra's Algorithm
Intuition\nThink of standing at $currentPosition$ and you have 4 possible directions to move. If you took $cost$ time to reach to a point where you are currentl
# Intuition\nThink of standing at $currentPosition$ and you have 4 possible directions to move. If you took $cost$ time to reach to a point where you are currently and you can move from $currentPosition$ to the $nextPosition$ using a $nextCost$ would you move if earlier you already visited the $nextPosition$ with some cost greater than $nextCost$? Will you do it? Ask yourself? This is optimisation on top of $Dijkshtra\'s$.\n\nAlternate movement can be a state while moving from one $currentPosition$ to the $nextPosition$.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialise $costDP$ matrix of size $(n,m)$ to maintain minimum cost taken to reach a position index **{x,y}**\n2. Initialise an increasing $priorityQueue$ with states **{cost, rowIndex, columnIndex, prevMove}** with values **{0,0,0,2}**\n3. $costDP[0][0]$ would be set to 0 and $prevMove$ will be set to 2\n4. Initialise $moves$ matrix with possible four directional positions\n5. Iterate on $priorityQueue$ till either it is not empty or you reach till $(n-1,m-1)$ position of $grid$\n6. $nextMove$ while iteration needs to be alternative so check what was $prevMove$ in $priorityQueue$ and assign it accordingly\n7. check whether $nextX$ $nextY$ is valid or not if it is valid check whether you can move from $currentPosition$ to the $nextPosition$ using a $nextCost$ would you move if earlier you already visited the $nextPosition$ with some cost greater than $nextCost$ our *Intuition*.\n8. push the **nextCost, nextX, nextY, nextMove** in $priorityQueue$ and repeat step *5*\n\n\nFor alternate movement between $1$ and $2$ maintain the $previousMove$ as a state in **priorityQueue** while implementing $Dijkshtra\'s$.\n\n# Complexity\n- Time complexity: $$O(n * m * log(m*n))$$\nWhere $n$: number of rows in grid\nand $m$: number of columns in grid\n\n- Space complexity: $$O(n*m)$$\nWhere $n$: number of rows in grid\nand $m$: number of columns in grid\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    #define tpiii tuple<int,int,int,int>\n\n    bool isValid(int R,int C, int x, int y) {\n        return x>=0&&x<R&&y>=0&&y<C;\n    }\n\n    int minTimeToReach(vector<vector<int>>& grid) {\n        priority_queue<tpiii, vector<tpiii>, greater<tpiii>>Q;\n        int R = grid.size();\n        int C = grid[0].size();\n\n        vector<vector<int>>costDP(R,vector<int>(C,INT_MAX));\n\n        Q.push({0,0,0,2});\n        costDP[0][0] = 0;\n\n        vector<vector<int>> moves = {\n            {0,1},\n            {1,0},\n            {0,-1},\n            {-1,0}\n        };\n\n\n        while(!Q.empty()) {\n            auto [cost, x, y, prevMove] = Q.top();\n            \n            int nextMove = (prevMove==1)?2:1;\n            if(x==R-1&&y==C-1) {\n                return cost;\n            }\n\n            Q.pop();\n\n            for(auto ele:moves) {\n                int nextX = ele[0] + x;\n                int nextY = ele[1] + y;\n                if(isValid(R,C, nextX, nextY)) {\n                    int nextCost = max(cost, grid[nextX][nextY]) + nextMove;\n                    if(nextCost<costDP[nextX][nextY]) {\n                        costDP[nextX][nextY] = nextCost;\n                        Q.push({nextCost, nextX, nextY, nextMove});\n                    }\n                }\n            }\n        }\n        return -1;\n    }\n};\n```
['Graph', 'Heap (Priority Queue)', 'Matrix', 'Shortest Path', 'C++']