Easy Dijkstra | Video solution | Intuition explained
Intuition\nDoes the solution always exist? \n\n# Approach\nQ. Is there any case where we can not reach the end? \nans: Yes!\n\nQ. That\'s the example test case 
# Intuition\nDoes the solution always exist? \n\n# Approach\nQ. Is there any case where we can not reach the end? \nans: Yes!\n\nQ. That\'s the example test case that has already been provided to us. The exact specifics are that if I can not go to (1,0) and even (0,1) from (0,0) then my answer doesn\'t exist! \nNow in what case it isn\'t possible for me to go to these 2 indices? \nans: Since grid[0][0]=0 hence when the value at (1,0) or (0,1) is greater than 1 itself then I would be blocked. \n\nQ. Is it possible for me to always reach the end otherwise? \nans: yes, let me prove this. Say we are at some node X it\'s parent node is P (all nodes except for (0,0) have a parent node). and from X we want to go to Y. Now 2 cases would arise \ncase1. currentTime(at which I am on X)+1>=VAL[Y], in this case the time I can simply go to Y. \ncase2. I\'ll go back and forth between X and P. 1 unit of time would be spent going from X to P and another to go from P to X. so a round trip would cost us 2 time units. Since we can perform any roundtrips this way hence we add 2*N time where N is the number of roundtrips! \nafter performing some number of roundtrips our time+1 would become greater than VAL[Y] and now I can go to Y! The only point to be noted is that when you peform these roundtrips then it\'s possible that you reach a valud of time t which is 1 more than the optimum value. let\'s say currTime=6, Val[Y]=8 so now you go from X to P and P to X and your time increases by 2 units. so you are at X now with currTime =6+2=8, you need 1 more unit of time to go to Y so you reach there at time 8+1=9 whereas the optimum time would\'ve been 8 units.\n\nVideo solution: https://youtu.be/FEl1u9FvHLE\n\n\n\nPS- code is not mine, I modified the code of some other contributer. \n# Complexity\n- Time complexity:\n- O(m*n*log(mn))\n- Space complexity:\n- O(mn)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n\n# Code\n```\nclass Solution {\npublic:\nint minimumTime(vector<vector<int>>& grid) {\n    // Check if the starting points are blocked\n    if (grid[0][1] > 1 && grid[1][0] > 1) return -1;\n    \n    int n = grid.size(), m = grid[0].size();\n    int dirs[]={1,0,-1,0,1};\n    int visited[n][m];\n    memset(visited,0,sizeof visited);\n    priority_queue<vector<int>, vector<vector<int>>, greater<>> pq;\n    \n    pq.push({grid[0][0], 0, 0}); // Start at top-left corner\n    while (!pq.empty()) {\n        // Get the current time, row, and column\n        int time = pq.top()[0], row = pq.top()[1], col = pq.top()[2];\n        pq.pop();\n        \n        if (row == n - 1 && col == m - 1) return time;\n        \n        if (visited[row][col]) continue;\n        visited[row][col] = true;\n        for (int i=0;i<4;i++) {\n            int r = row + dirs[i], c = col + dirs[i+1];\n            if (r < 0 || r >= n || c < 0 || c >= m || visited[r][c]) continue;\n            int wait = (grid[r][c] - time) % 2 == 0?1:0; // we would have to wait 1 more extra unit of time if the difference was already odd. \n            pq.push({max(grid[r][c] + wait, time + 1), r, c});\n        }\n    }\n    return -1; \n}\n};\n```
['C++']