Python || Dijkstra Variant || Explained
There is only one case where we can\'t reach last cell , i.e. when all cells adjacent to (0,0) are greater than 1.\nOtherwise we can always keep switching betwe
There is only one case where we can\'t reach last cell , i.e. when all cells adjacent to (0,0) are greater than 1.\nOtherwise we can always keep switching between current cell and the last visited cell to pass the time.\nNow when we are moving from one cell to its adjacent cell -\n1) if the difference between grid value of new cell and current cost is odd and grid value is greater than cost then we can move to new cell with it\'s required grid value.\n2) otherwise if difference is even and new cell grid value is greater than cost then we can only reach it by grid value+1 (since we will need 1 extra move while swtiching between current and previously visited cell).\n3) If grid value of new cell is less than or equal to current cost then we can always move to new cell with new_cost=cost+1 (This is normal bfs move) .\n\nTime Complexity - O(m* n * log (m* n))\n\nCode : \n```\nclass Solution:\n    def minimumTime(self, grid: List[List[int]]) -> int:\n        m,n=len(grid),len(grid[0])\n        directions=((0,1),(1,0),(-1,0),(0,-1))\n        i,j,flag=0,0,0\n        for di,dj in directions:\n            ni,nj=i+di,j+dj\n            if 0<=ni<m and 0<=nj<n and grid[ni][nj]<=1: flag=1;break;\n        if not flag: return -1\n        heap=[]\n        heappush(heap,(0,0,0))\n        dist=[[sys.maxsize]*n for _ in range(m)]\n        while heap:\n            cost,i,j=heappop(heap)\n            if i==m-1 and j==n-1: return cost\n            for di,dj in directions:\n                ni,nj=i+di,j+dj\n                if 0<=ni<m and 0<=nj<n:\n                    new_cost=cost+1\n                    if grid[ni][nj]>cost:\n                        if abs(cost-grid[ni][nj])%2==0:\n                            new_cost=grid[ni][nj]+1\n                        else:\n                            new_cost=grid[ni][nj]\n                    if new_cost<dist[ni][nj]:\n                        dist[ni][nj]=new_cost\n                        heappush(heap,(new_cost,ni,nj))\n        \n                \n```
['Breadth-First Search', 'Heap (Priority Queue)', 'Python', 'Python3']