Assassin Reaches the Exit

Reported in interviews at Hudson River Trading

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),
  • G a guard (impassable),
  • S the assassin's starting cell (exactly one),
  • E the 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.

Related free problems