C++ || Modified Dijkstra's Algorithm || Explained Approach || Commented code
Intuition\n Describe your first thoughts on how to solve this problem. \nSome sort of modified dijkstra\'s algorth will be used.\n# Approach\n Describe your app
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSome sort of modified dijkstra\'s algorth will be used.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nMODIFICATION of DIJKSTRA\'S ALGO :-\n\nWe will mainatain a time visited 2d array for keeping the track of minimum time to reach the node.\nDifferent cases will occur :\n1. the grid node is not yet visited && current time >= grid node time    :   simply upgarde the time array and push values in minheap.\n2. the grid node is not yet visited && current time < grid node time    :   check the difference btw current time and grid node time ; it its even -> use grid node time in time array and push values in minheap , and if odd -> use grid node time + 1 in time array and push values in minheap.\n3. the grid node is visited before && current time < time matrix value : here arise two subcases :-\n3.a. if grid node value <= current time : simply upgarde the time array and push values in minheap.\n3.b. if grid node value > current time : arise two sub-subcases :  check the difference btw current time and grid node time :-\n3.b.1. if it its even -> use grid node time in time array and push values in minheap .\n3.b.2. if its odd -> use grid node time + 1 in time array and push values in minheap. \n\n\n![download (2).jfif](https://assets.leetcode.com/users/images/74b13bd5-b9e2-40cc-9843-1503daedf32c_1677453378.4892983.jpeg)\n\n\n \n# Complexity\n- Time complexity   :   O(mn * (mn)log(mn))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity  :   O(n*m) \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    typedef pair<int,pair<int,int>> p;\n    \n    int minimumTime(vector<vector<int>>& grid) {\n        int n = grid.size();\n        int m = grid[0].size();\n        \n        //case when no moves can be made [can\'t reach the destination]\n        if(grid[0][1]>1 && grid[1][0]>1)   return -1;\n        \n        //helping matrices\n        vector<vector<int>> time(n, vector<int> (m,INT_MAX));\n        vector<int> drow {0,-1,0,1};\n        vector<int> dcol {-1,0,1,0};\n        \n        //minHeap for dijkstra\'s\n        priority_queue<p,vector<p>,greater<p>> q;\n        //pushing initial values of source\n        q.push({0,{0,0}});\n        time[0][0] = 0;\n        int res = INT_MAX;\n        \n        while(!q.empty())   {\n            auto it = q.top();\n            q.pop();\n            int r = it.second.first;\n            int c = it.second.second;\n            int t = it.first;\n            \n            //case when destination is reached (possible answer)\n            if(r==n-1 && c==m-1)    \n                res = min(res,t);\n            \n            //incrementing time for the next new moves\n            t++;\n            \n            //checking all four directions\n            for(int i=0; i<4; i++)  {\n                int dr = r+drow[i];\n                int dc = c+dcol[i];\n                \n                if(dr>=0&&dr<n&&dc>=0&&dc<m) {\n                    if(time[dr][dc]==INT_MAX)   {\n                        //case 1\n                        if(grid[dr][dc]<=t) {\n                            time[dr][dc] = t;\n                            q.push({t,{dr,dc}});\n                        }\n                        //case 2\n                        else {\n                            int dif = grid[dr][dc]-t;\n                            if(dif%2==0)    {\n                                time[dr][dc] = grid[dr][dc];\n                                q.push({grid[dr][dc],{dr,dc}});\n                            }\n                            else {\n                                time[dr][dc] = grid[dr][dc]+1;\n                                q.push({grid[dr][dc]+1,{dr,dc}});\n                            }\n                        }\n                    }\n                    else {\n                        if(time[dr][dc]>t)  {\n                            //case 3.a\n                            if(grid[dr][dc]<=t)  {\n                                time[dr][dc] = t;\n                                q.push({t,{dr,dc}});                                \n                            }\n                            //case 3.b\n                            else {\n                                int dif = grid[dr][dc]-t;\n                                if(dif%2==0)    {\n                                    time[dr][dc] = grid[dr][dc];\n                                    q.push({grid[dr][dc],{dr,dc}});\n                                }\n                                else {\n                                    time[dr][dc] = grid[dr][dc]+1;\n                                    q.push({grid[dr][dc]+1,{dr,dc}});\n                                }\n                            }\n                        }\n                    }\n                }\n            }\n        }\n        \n        if(res==INT_MAX)\n            return -1;\n        return res;\n    }\n};\n```\n\n![sad-thumbs-up-cat.3.meme.webp](https://assets.leetcode.com/users/images/ac9176bf-ce84-48a7-ac3e-74b0ba735101_1677453394.161722.webp)\n\n\n
['Breadth-First Search', 'Matrix', 'Shortest Path', 'C++']