BFS + PriorityQueue
Intuition\nOn every step we will go to cell we can visit at minimum time.\n\n# Approach\nWe will use BFS + priority queue. Among all possible cells we select on
# Intuition\nOn every step we will go to cell we can visit at minimum time.\n\n# Approach\nWe will use BFS + priority queue. Among all possible cells we select one we can reach at minimum time. How can we calculate minimum time we can reach particular cell. Let consider following example:\n![Screenshot 2023-02-26 at 17.22.43.png](https://assets.leetcode.com/users/images/c3f3d24c-7cfc-4733-b08f-1b8df2719f17_1677432207.830003.png)\nFrom [0,0] we can move to [0,1] at minute 1. At minute 2 we can move to [1,1] at minute 2. At minute 3 we can move to [1,2]. Let calculate at what minute we can move to cell [1,3]. We can not move to it instantly but we can move back and forward untill we can. So we move back to [1,1] at minute 4, move to [1,2] at minute 5 and move to [1,3] at minute 6. We seond 2 seconds to do step back/forward. So if at time N we considering move to grid[i][j] = M we can calculate minimum time to reach it as following:\n```javascript\nif N + 1 >= M\n  time = N + 1\nelse\n  diff = M - N -1 // seconds we need to wait untill we can move to this cell\n  time = diff MOD 2 == 0 ? M : M + 1 // We spend 2 seconds to do step back/forward so if difference is even we can move at M if not at M + 1\n```\n**No Path**\nThere is only one case when there is now path when both first possible steps [0,1] and [1,0] greater than 1. In this case we can not move. In all other cases we can do step back/forward in any particular cell untill next cell is avalalbe to move in.\n\n# Complexity\n- Time complexity:\nO(N*Log(N))\n\n- Space complexity:\nO(N)\n\n# Code\n```\n/**\n * @param {number[][]} grid\n * @return {number}\n */\nlet visited = new Set()\nconst moves = [[0, -1], [0, 1], [1, 0], [-1, 0]]\nvar minimumTime = function(grid) {\n    visited = new Set();\n    // Check if there is no path\n    if(grid[0][1] > 1 && grid[1][0] > 1){\n        return -1\n    }\n    \n    return solve(grid)\n};\n\nfunction solve(grid){\n    const heap = new MinPriorityQueue()\n    heap.enqueue([0, 0, 0], 0)\n    while(heap.size() > 0){\n        let c = heap.dequeue().element\n        let i = c[0]\n        let j = c[1]\n        let key = `${i}_${j}`\n        visited.add(key)\n        let time = c[2]\n        if(i == grid.length -1 && j == grid[0].length-1) {\n            return time\n        }\n        const nm = moves.map(m => [i + m[0], j + m[1]]).filter(m => m[0] >= 0 && m[1] >= 0 && m[0] < grid.length && m[1] < grid[0].length).filter(m => !visited.has(`${m[0]}_${m[1]}`))\n        \n        for(let m of nm) {\n            let nt = time+1\n            if(time + 1 < grid[m[0]][m[1]]) {\n                let diff = grid[m[0]][m[1]] - time-1\n                nt = diff % 2 == 0 ? \n                    grid[m[0]][m[1]] : grid[m[0]][m[1]] + 1\n                \n            }\n            visited.add(`${m[0]}_${m[1]}`)\n            heap.enqueue([...m, nt], nt)\n        }\n    }\n    return -1;\n}\n\n\n```
['JavaScript']