Beats 61% Python dijkstra, edge cases explained with examples SUPER CLEAR!
Intuition\n Describe your first thoughts on how to solve this problem. \nDijkstra in 2d matrix with edge cases, do this problem first.\nhttps://leetcode.com/pro
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nDijkstra in 2d matrix with edge cases, do this problem first.\nhttps://leetcode.com/problems/swim-in-rising-water/\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThere are 2 cases:\nThe current time allows us to visit the neighboring cell, then we simply increment time by 1 and visit that cell if it is a minimum according to dijkstra algorithm.\n\nThe other case is if the current time + 1 does not hit the allowed time.\nThen, the difference matters. To stall the time, we can move from the cell we are at to the cell to the left or up or down (doesn\'t really matter in principle) back and forth. \n\nIf the difference between the next cell and current time is even, we have to add an extra one. \nFor example, if current time is t=1 and we are trying to go to 5, \nwe go left (t = 2), right (t=3), left(t=4), right(t=5) (but we are still at the original cell), so we add 1 more to move to the next cell.\n\nif current time is t=1 and we are trying to go to 4, \nwe go left (t = 2), right (t=3), and then we can directly go right again to 4. \n\nThus \n```\ndiff = grid[newx][newy] - currTime \nif diff%2 == 0:\n    newTime = grid[newx][newy] + 1\nelse:\n    newTime = grid[newx][newy]\n```\nhandles this edge case.\n# Complexity\n- Time complexity:\n$$O(M*Nlog(M*N))$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(M*N)$$\n# Code\n```python3 []\nclass Solution:\n    def minimumTime(self, grid: List[List[int]]) -> int:\n        #dijkstra\n        if grid[0][1] > 1 and grid[1][0] > 1: #cant move from start \n            return -1\n\n        directions = [(1,0), (0, 1), (-1,0), (0, -1)]\n        minheap = [(0, 0, 0)]\n        m = len(grid)\n        n = len(grid[0])\n        minTime = [[float(\'inf\') for _ in range(n)] for _ in range(m)]\n\n        while minheap:\n            currTime, x, y = heappop(minheap)\n            if x == m-1 and y == n-1: #reached end\n                return currTime\n\n            for dx, dy in directions:\n                newx = x+dx\n                newy = y+dy\n\n                if 0<=newx<m and 0<=newy<n:\n                    if grid[newx][newy] <= currTime+1 and currTime+1 < minTime[newx][newy]:\n                        minTime[newx][newy] = currTime+1\n                        heappush(minheap, (currTime+1, newx, newy))\n                    \n                    diff = grid[newx][newy] - currTime \n                    if diff%2 == 0:\n                        newTime = grid[newx][newy] + 1\n                    else:\n                        newTime = grid[newx][newy]\n\n                    if grid[newx][newy] > currTime+1 and newTime < minTime[newx][newy]:\n                        minTime[newx][newy] = newTime\n                        heappush(minheap, (newTime, newx, newy))\n        return -1 #cant reach end\n```
['Python3']