Assassin Reaches the Exit
Problem statement
An assassin starts on a grid and wants to reach the exit. You are given the grid as a list of strings (all the same length), where each cell is one of:
.an open cell the assassin may stand on,#a wall (impassable),Ga guard (impassable),Sthe assassin's starting cell (exactly one),Ethe exit cell (exactly one).
From any cell the assassin may move one step up, down, left, or right (4-directionally) into an open cell, the exit, or the start, but never into a wall # or a guard G, and never off the grid. Return True if the assassin can reach E from S, and False otherwise.
Implement:
def canReach(grid):
...
where grid is a list of equal-length strings. Return a boolean.
Constraints: $1 \le \text{rows}, \text{cols} \le 10^3$. There is exactly one S and exactly one E.
Example: grid = ["S.#", ".G.", "..E"]. From S at $(0,0)$ the assassin can go down to $(1,0)$, down to $(2,0)$, right to $(2,1)$, and right to E at $(2,2)$, avoiding the guard G at $(1,1)$ and the wall # at $(0,2)$, so the answer is True.
Counter-example: grid = ["S#E", "###", "..."] returns False, because the wall row and the # between S and E seal off the exit.
Show hint
Once you ignore the story, what classic graph question about a grid is being asked?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.