Djackstra Solution Visualisation, Commented solution
\n# Intuition\n Describe your first thoughts on how to solve this problem. \n\nIf you find this useful please give it an upvote!\nSince we have to find the mini
\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n**If you find this useful please give it an upvote!**\nSince we have to find the minimum time and we have to search it. This boils down to **BFS**. However, we have to approach it greedily so we should use **djackstra\'s algorithm which uses minimum Priority_queue\ninstead of queue in bfs**.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nwe start from `{0,0}`;\nThere are 4 cases that are possible:\n![image.png](https://assets.leetcode.com/users/images/afe87c19-723a-4246-bfcf-49f8f5edb767_1677385952.6621647.png)\n* If we are at red block at `time=3 sec`, we can move to yellow block at `time=4 sec`. \n \n![image.png](https://assets.leetcode.com/users/images/66c04bcf-2794-4130-96e0-c43379766157_1677385852.6977856.png)\n* If we are at red block at t=1 sec and want to move to block 5\nwe can keep on moving `1->0->1->0->1->1` until we move back to 1 at 5 sec and in that case we move to block 5 at t=7 sec.grid[X][Y]+1\n(if difference is **even**, we reach at `grid[X][Y]+1`)\n\n![image.png](https://assets.leetcode.com/users/images/d9cb0ca4-6212-458c-b903-eeb92e6af6bf_1677385796.133826.png)\n* To reach from 0 to 4 we keep on moving `0->1->0->1` until at red block and reach it at t=4sec.  \n(if difference is **odd**, we reach at `grid[X][Y]`)\n\n![image.png](https://assets.leetcode.com/users/images/bc80be8a-7186-4eaa-a745-f01cb3b38a21_1677385927.8410172.png)\n* If we are at `{0,0}`  and we have these two cases above we cannot move to any and in this case we will `return -1`;(edge case).\n\n\n* **Visited array** keeps into account **minimum time instant at which we reach that position X,Y**. If it is smaller than current instant `par[0]+1>=visited[X][Y]` we dont add it in our priority_queue.\n# Complexity\n- Time complexity: O(m*n log(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\nclass Solution {\npublic:\n    int dir[5]={1,0,-1,0,1};\n    int visited[1001][1001];  //keeps the minimum instant we reached a point X,Y.\n    int minimumTime(vector<vector<int>>& grid) \n    {\n        \n        int m=grid.size(),n=grid[0].size();      \n        if(grid[0][1]>1 and grid[1][0]>1) //edgecase: \n            return -1;  \n        for(int i=0;i<m;i++)\n            for(int j=0;j<n;j++)\n                visited[i][j]=INT_MAX;#initialise visted to INT_MAX.           \n        priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>pq;  \n#initialise min priority queue for djackstra traversal\n        pq.push({0,{0,0}});\n        visited[0][0]=0; #starting position\n        while(!pq.empty())\n        {\n            auto temp=pq.top();\n            int par[3]={temp.first,temp.second.first,temp.second.second};     // par[0]->time,par[1]->  i, par[2]-> j\n            if(par[1]==m-1 and par[2]==n-1)\n                return par[0];\n            pq.pop();\n            for(int k=0;k<4;k++)\n            {\n                int X=par[1]+dir[k];\n                int Y=par[2]+dir[k+1];\n                if(X<0||Y<0||X==m||Y==n||par[0]+1>=visited[X][Y])\n                    continue;  //do not visit is we go out of boundary, or reach node if we have only reached there at smaller time\n                int time=0;\n                if(par[0]+1>grid[X][Y]) time=par[0]+1; //if we reach at time instant greater\n#than grid[X][Y] time will be par[0]+1; \n                else if((grid[X][Y]-par[0])%2) time=grid[X][Y]; //if diff between the two times is odd we will reach that node in time =grid[X][Y];\n                else time=grid[X][Y]+1; //if diff between the two times is even we will reach that node in time =grid[X][Y]+1;\n                pq.push({time,{X,Y}});\n                visited[X][Y]=time; #update time\n            }\n        }\n        return -1;\n    }\n};\n```
['Shortest Path', 'C++']