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

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.