Grid Reachability with a Forbidden Turn
Amazon● MediumFULLTIMEPHONE SCREENProblem statement
Determine whether a destination can be reached on an obstacle grid while respecting movement direction.
For this exercise, assume grid contains 0 for open cells and X for blocked cells. start and destination are zero-based [row, column] coordinates of open cells.
initialHeading is 0 for north, 1 for east, 2 for south, or 3 for west. forbiddenTurn is left or right.
Each move advances exactly one adjacent cell. Relative to the current heading, you may continue straight or turn 90 degrees in the direction that is not forbidden. You cannot reverse direction, enter a blocked cell, or leave the grid. Your heading becomes the direction of the move. Reaching the destination with any heading succeeds. Starting at the destination succeeds with zero moves.
Return whether a valid path exists.
Function
canReachWithTurnRule(grid: String[], start: int[], destination: int[], initialHeading: int, forbiddenTurn: String) → booleanExamples
Example 1
grid = ["000","0X0","000"]start = [0,0]destination = [2,2]initialHeading = 1forbiddenTurn = "left"return = trueMove east along the top row, turn right, and continue south.
Example 2
grid = ["000","0X0","000"]start = [0,0]destination = [2,2]initialHeading = 1forbiddenTurn = "right"return = falseThe only open route from the top-left corner requires a right turn, which is forbidden.
Constraints
- For this exercise, assume
1 <= rows, columns <= 500; all rows have equal length. - Every cell is
0orX. - Start and destination are valid open cells.
0 <= initialHeading <= 3.forbiddenTurnisleftorright.