Reach the last cell in the least time

A simple approach will be to assume the time required to reach ‘(n - 1, n - 1)’ as ‘0’. Now traverse the grid from ‘(0, 0)’ and see if we can reach the last cell. If we cannot reach the last cell, then increment the time required by ‘1’ and keep increasing the time until we can reach the last cell. Following is an implementation using BFS traversal:

• Set ‘time = 0’. Use this to store the time required to reach the last cell ‘(n - 1, n - 1)’.
• Run a loop until ‘bfs(time)’ is not equal to true:
  • ‘time += 1’. We increase the time so that more cells are unlocked and again try to reach the last node.
• Return ‘time’ as the answer.

The ‘bfs(integer time)’ function:

• Create a 2-d array ‘seen[n][n]’ with each element set to ‘false’. Use it to mark the visited cells in the BFS traversal.
• Create a queue ‘bfsQ’. Use it to perform the BFS traversal.
• Initialize ‘dir[4][2] = [(1, 0), (-1, 0), (0, 1), (0, -1)]. Add ‘dir[i]’ to a cell to move to an adjacent cell.
• Push ‘(0, 0)’ in ‘bfsQ’ and set ‘seen[0][0] = true’ (the source node).
• Run a loop until ‘bfsQ’ is not empty:
  • ‘(x, y) = bfsQ.pop()’. Get the location of the cell in front of the queue and pop it.
  • Run a loop where ‘i’ ranges from ‘0’ to ‘3’:
    • ‘newX = x + dir[i][0]’ and ‘newY = y + dir[i][0]’. The location of adjacent cell.
    • If (‘(newX, newY)’ is a valid cell) and (‘seen[newX][newY]’ is false) and (‘grid[newX][newY] <= time’), then the adjacent cell is valid and reachable from ‘(x, y)’:
      • If ‘newX = n - 1’ and ‘newY = n - 1’, then we have reached the last cell:
        • Return true.
      • ‘seen[newX][newY] = true’
      • Push ‘(newX, newY)’ in ‘bfsQ’.
• Return false, as we were unable to reach the last cell.

Instead of linearly searching for the least time value, we can do a binary search. In binary search, if we cannot reach the last cell for the current value of time (i.e., ‘mid’), we search for a greater time value because more cells get unlocked as time passes. If we reach a value of time for which the last cell is reachable, we store this value as the answer and search if an even lower value of time is possible. In the following implementation, we use BFS to check if the last cell is reachable.

• Set ‘low = grid[0][0]’. Lowest possible time value.
• Set ‘high = (n ^ 2) - 1’. Highest possible time value.
• Run a loop until ‘low’ is less than ‘high’:
  • ‘mid = (low + high)/2’
  • If ‘reachable(mid)’ is true, then the last cell is reachable at the time ‘mid’:
    • ‘high = mid’
  • Else:
    • ‘low = mid + 1’
• Return ‘low’ as the answer.

The ‘reachable(integer time)’ function using BFS:

• Create a 2-d array ‘seen[n][n]’ with each element set to ‘false’. Use it to mark the visited cells in the BFS traversal.
• Create a queue ‘bfsQ’. Use it to perform the BFS traversal.
• Initialize ‘dir[4][2] = [(1, 0), (-1, 0), (0, 1), (0, -1)]. Add ‘dir[i]’ to a cell to move to an adjacent cell.
• Push ‘(0, 0)’ in ‘bfsQ’ and set ‘seen[0][0] = true’ (the source node).
• Run a loop until ‘bfsQ’ is not empty:
  • ‘(x, y) = bfsQ.pop()’. Get the location of the cell in front of the queue and pop it.
  • Run a loop where ‘i’ ranges from ‘0’ to ‘3’:
    • ‘newX = x + dir[i][0]’ and ‘newY = y + dir[i][0]’. The location of adjacent cell.
    • If (‘(newX, newY)’ is a valid cell) and (‘seen[newX][newY]’ is false) and (‘grid[newX][newY] <= time’), then the adjacent cell is valid and reachable from ‘(x, y)’:
      • If ‘newX = n - 1’ and ‘newY = n - 1’, then we have reached the last cell:
        • Return true.
      • ‘seen[newX][newY] = true’
      • Push ‘(newX, newY)’ in ‘bfsQ’.
• Return false, as we were unable to reach the last cell.

Consider an approach similar to Dijkstra’s shortest path algorithm, in each iteration instead of adding the adjacent node with a smaller edge value, we add the node with a smaller node value (i.e., unlock time). In this way, the time required to reach the last node ‘(n - 1, n - 1)’ will be the least possible time value.

Use a priority queue (in this case a min-heap) to maintain a list of cells that are adjacent to the visited cells. Maintain a variable ‘time’ which stores the time required to reach the visited cells. Initially, ‘time = grid[0][0] as only the cell ‘(0, 0)’ is visited, push all its adjacent cells in the priority queue. In each subsequent iteration, pop the cell with the smallest unlock time, add its adjacent cells that are unvisited to the priority queue, and if its unlock time is more than ‘time’ the update ‘time’. Stop the algorithm when we reach the cell ‘(n - 1, n - 1)’ and update ‘time’, the new ‘time’ value will be the answer.

• Set ‘time = 0’. Use this to store the time required to reach the last cell ‘(n - 1, n - 1)’.
• Create a 2-d array ‘seen[n][n]’ with each element set to ‘false’. Use it to mark the visited cells.
• Create a priority queue ‘pq’ that stores an element of type cell (‘{unlock time, x-position, y-position}’), and the cell with a smaller ‘time’ value is given higher priority.
• Initialize ‘dir[4][2] = [(1, 0), (-1, 0), (0, 1), (0, -1)]. Add ‘dir[i]’ to a cell to move to an adjacent cell.
• Push ‘{grid[0][0], 0, 0}’ in ‘pq’ and set ‘seen[0][0] = true’ (the source node).
• Run a loop until ‘pq’ is not empty:
  • ‘cur = pq.pop()’. Get the cell with the smallest time value and pop it.
  • ‘time = max(time, cur->time)’
  • Run a loop where ‘i’ ranges from ‘0’ to ‘3’:
    • ‘newX = cur.x + dir[i][0]’ and ‘newY = cur.y + dir[i][0]’. The location of adjacent cell.
    • If (‘(newX, newY)’ is a valid cell) and (‘seen[newX][newY]’ is false), then:
      • If ‘newX = n - 1’ and ‘newY = n - 1’, then we have reached the last cell:
        • Return ‘max(time, grid[newX][newY])’ as the answer.
      • ‘seen[newX][newY] = true’
      • Push ‘{grid[newX][newY], newX, newY}’ in ‘pq’.
• Return time.