Quick Overview

Decide whether a robot on a grid with blocked cells can travel from a start cell to a destination when it may never reverse direction and may only make the turns it is allowed. It tests modeling movement rules as a state space that includes the heading, and searching that space correctly on grids up to 200 by 200.

Grid Reachability for a Robot That Cannot Reverse and Has Restricted Turns

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

A robot moves on a rectangular grid given as a list of equal-length strings. Each character is one cell: - `'0'`: an open cell - `'X'`: a blocked cell - `'S'`: the start, which is an open cell - `'D'`: the destination, which is an open cell The robot always faces one of the four directions (up, down, left, right) and moves one cell per step. It may never go back the way it is heading, that is, it may never step in the direction opposite to the one it is facing. Which turns it may make is given by the string `allowed_turns`, which contains `'L'` if the robot may turn left, `'R'` if it may turn right, both letters, or neither. Return `True` if the robot can reach the destination from the start under these rules, and `False` otherwise. ### Function Signature ```python def can_reach(grid: list[str], allowed_turns: str) -> bool: ``` ### Rules - Row `0` is the top row and column `0` is the leftmost column. "Up" means toward row `0` and "left" means toward column `0`. - The robot starts on `S` without a heading, so its first step may go to any of the four neighbors of `S`. - After that, if the robot faces direction `h`, its next step goes one cell straight ahead in direction `h`; or one cell in the direction 90 degrees to the left of `h`, only if `'L'` is in `allowed_turns`; or one cell in the direction 90 degrees to the right of `h`, only if `'R'` is in `allowed_turns`. After every step, the robot faces the direction it just moved in. - Left and right are relative to the robot's heading. For example, a robot facing up that turns left moves toward column `0` and then faces left; a robot facing up that turns right moves toward the last column and then faces right. - Turning in place without moving is not possible, and stepping in the direction opposite to the current heading is never allowed. - A step must stay inside the grid and must not enter an `'X'` cell. - The robot may enter any open cell, including `S`, any number of times and with any heading. There is no limit on the number of steps. - The destination counts as reached as soon as the robot enters it, whatever its heading. ### Constraints - `1 <= len(grid) <= 200` - `1 <= len(grid[i]) <= 200`, and all rows have the same length. - Every character of every row is one of `'0'`, `'X'`, `'S'` and `'D'`. - The grid contains exactly one `'S'` and exactly one `'D'`. - `allowed_turns` is exactly one of `""`, `"L"`, `"R"` and `"LR"`. - The answer is a single boolean, uniquely determined by the input. ### Examples **Example 1** - Input: `grid = ["000000", "0X00D0", "0000X0", "0SX000"]`, `allowed_turns = "R"` - Output: `True` - Explanation: Using (row, column) coordinates, `S` is at (3, 1) and `D` is at (1, 4). The robot steps left to (3, 0); turns right, now facing up, to (2, 0); goes straight to (1, 0) and (0, 0); turns right, now facing right, to (0, 1); goes straight to (0, 2), (0, 3) and (0, 4); and turns right, now facing down, into `D` at (1, 4). **Example 2** - Input: `grid = ["000000", "0X00D0", "0000X0", "0SX000"]`, `allowed_turns = "L"` - Output: `False` - Explanation: With only left turns, every position the robot can reach lies among the cells (2, 0), (2, 1), (3, 0) and (3, 1), so it never gets near `D`. **Example 3** - Input: `grid = ["S00", "XXD"]`, `allowed_turns = ""` - Output: `False` - Explanation: The only possible first step is right, to (0, 1). Without turns, the robot can then only continue right to (0, 2), where going straight would leave the grid. Reaching `D` at (1, 2) would need a right turn.

Overview: Decide whether a robot on a grid with blocked cells can travel from a start cell to a destination when it may never reverse direction and may only make the turns it is allowed. It tests modeling movement rules as a state space that includes the heading, and searching that space correctly on grids up to 200 by 200.

Read the full Amazon Software Engineer interview experience this question came from

A robot moves on a rectangular grid. The grid is given as a list of equal-length strings `grid`, where each string is one row and each character is one cell: - `'0'`: an open cell - `'X'`: a blocked cell - `'S'`: the start, which is an open cell - `'D'`: the destination, which is an open cell The robot always faces one of the four directions (up, down, left, right) and moves exactly one cell per step. It may never step in the direction opposite to the one it is facing. The string `allowed_turns` says which turns it may make: it contains `'L'` if the robot may turn left, `'R'` if it may turn right, both letters, or neither. Implement `can_reach(grid, allowed_turns)` and return `True` if the robot can reach the destination from the start under the rules below, and `False` otherwise. ### Rules - Row `0` is the top row and column `0` is the leftmost column. "Up" means toward row `0` and "left" means toward column `0`. - The robot starts on `S` without a heading, so its first step may go to any of the four neighbors of `S`. - After that, if the robot faces direction `h`, its next step goes one cell straight ahead in direction `h`; or one cell in the direction 90 degrees to the left of `h`, only if `'L'` is in `allowed_turns`; or one cell in the direction 90 degrees to the right of `h`, only if `'R'` is in `allowed_turns`. After every step, the robot faces the direction it just moved in. - Left and right are relative to the robot's heading. For example, a robot facing up that turns left moves toward column `0` and then faces left; a robot facing up that turns right moves toward the last column and then faces right. - Turning in place without moving is not possible, and stepping in the direction opposite to the current heading is never allowed. - A step must stay inside the grid and must not enter an `'X'` cell. - The robot may enter any open cell, including `S`, any number of times and with any heading. There is no limit on the number of steps. - The destination counts as reached as soon as the robot enters it, whatever its heading. ### Constraints - `1 <= len(grid) <= 200` - `1 <= len(grid[i]) <= 200`, and all rows have the same length. - Every character of every row is one of `'0'`, `'X'`, `'S'` and `'D'`. - The grid contains exactly one `'S'` and exactly one `'D'`. - `allowed_turns` is exactly one of `""`, `"L"`, `"R"` and `"LR"`. - The answer is a single boolean, uniquely determined by the input. ### Example 1 ```text Input: grid = ["000000", "0X00D0", "0000X0", "0SX000"], allowed_turns = "R" Output: True ``` Using (row, column) coordinates, `S` is at (3, 1) and `D` is at (1, 4). The robot steps left to (3, 0); turns right, now facing up, to (2, 0); goes straight to (1, 0) and (0, 0); turns right, now facing right, to (0, 1); goes straight to (0, 2), (0, 3) and (0, 4); and turns right, now facing down, into `D` at (1, 4). ### Example 2 ```text Input: grid = ["000000", "0X00D0", "0000X0", "0SX000"], allowed_turns = "L" Output: False ``` With only left turns, every position the robot can reach lies among the cells (2, 0), (2, 1), (3, 0) and (3, 1), so it never gets near `D`. ### Example 3 ```text Input: grid = ["S00", "XXD"], allowed_turns = "" Output: False ``` The only possible first step is right, to (0, 1). Without turns, the robot can then only continue right to (0, 2), where going straight would leave the grid. Reaching `D` at (1, 2) would need a right turn.

Constraints

  • 1 <= len(grid) <= 200
  • 1 <= len(grid[i]) <= 200, and all rows have the same length.
  • Every character of every row is one of '0', 'X', 'S' and 'D'.
  • The grid contains exactly one 'S' and exactly one 'D'.
  • allowed_turns is exactly one of "", "L", "R" and "LR".
  • The answer is a single boolean, uniquely determined by the input.

Examples

Input: (['000000', '0X00D0', '0000X0', '0SX000'], 'R')

Expected Output: True

Explanation: Source Example 1: right turns take the robot around the obstacles and into D from above.

Input: (['000000', '0X00D0', '0000X0', '0SX000'], 'L')

Expected Output: False

Explanation: Source Example 2: with only left turns the robot stays among (2,0), (2,1), (3,0) and (3,1).

Hints

  1. Knowing only which cell the robot is on is not enough to know where it can go next. What else determines its legal moves?
  2. The same cell can be worth visiting again if the robot arrives facing a different direction, so think about what a 'state' of the search should be.
  3. The start is special because it has no heading yet; handle its first step separately, then run an ordinary graph search over the remaining states.

Loading coding console...

Show the approach

Approach

Model the robot as a state (row, column, heading). Where the robot can go next depends on both its cell and the direction it faces, so reachability is a graph search over at most 4 * R * C states, where R and C are the numbers of rows and columns.

Number the directions clockwise: up = 0, right = 1, down = 2, left = 3. From heading h, going straight keeps h, a right turn gives (h + 1) mod 4 and a left turn gives (h + 3) mod 4. The reverse direction (h + 2) mod 4 is never generated, which enforces the no-U-turn rule. The set of offsets {0}, plus 3 if 'L' is allowed and 1 if 'R' is allowed, is computed once from allowed_turns.

The start has no heading, so it is expanded separately: each of the four neighbors of S that lies inside the grid and is not 'X' becomes the state (neighbor, direction of that step). Then a breadth-first search pops a state (r, c, h) and tries each allowed direction d = (h + offset) mod 4. A move is legal when the next cell is inside the grid and not 'X'. If that cell is 'D', the answer is True immediately, because the destination counts as reached on entry, with any heading. Otherwise the state (next cell, d) is enqueued unless it has been seen before. If the queue empties without entering D, no sequence of legal moves reaches it, so the answer is False.

Correctness: every legal walk of the robot is a path in this state graph and every path in the graph is a legal walk, so the search finds D exactly when some walk reaches it. Marking visited per (cell, heading), not per cell, matters: a robot that may only turn left can pass a cell once facing up and later come back facing right after circling a 2x2 block, and only the second visit may lead to D. Re-entering S is allowed and handled like any other open cell; it never helps, because the heading-free first step from S already covers every direction.

Each state is enqueued at most once and has at most three outgoing moves, so the work is linear in the number of cells.

Time complexity:
O(R * C), where R = len(grid) and C = len(grid[0]); at most 4 * R * C (cell, heading) states, each with at most 3 moves
Space complexity:
O(R * C) for the visited array and the queue over (cell, heading) states