Can the character reach the destination?
Company: Roblox
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You control a character starting at a start cell and want to reach a target cell in a 2D grid. Some cells are blocked by obstacles and cannot be entered.
Given a grid of size m x n containing:
- 'S' = start (exactly one)
- 'T' = target (exactly one)
- '#' = obstacle (cannot step on)
- '.' = free cell
The character may move one step at a time in 4 directions (up, down, left, right) and must stay within the grid.
Return whether it is possible to reach 'T' starting from 'S'.
Quick Answer: This question evaluates understanding of graph traversal and reachability in grid-based pathfinding, covering skills such as modeling a 2D grid as a graph, handling obstacles and boundary conditions, and algorithmic traversal strategies.
You are given a 2D grid representing a map. There is exactly one start cell 'S' and exactly one target cell 'T'. Some cells contain obstacles '#', which cannot be entered, and free cells are marked with '.'.
The character starts at 'S' and can move one step at a time in four directions: up, down, left, and right. The character must stay inside the grid and cannot move onto obstacle cells.
Return whether it is possible to reach 'T' starting from 'S'.
Constraints
- 1 <= m, n
- All rows in grid have the same length
- grid[i][j] is one of 'S', 'T', '#', or '.'
- Exactly one 'S' and exactly one 'T' exist in the grid
Examples
Input: (["S..", ".#.", "..T"],)
Expected Output: True
Explanation: A valid path exists around the obstacle: down, down, right, right.
Input: (["S#.", "##.", "..T"],)
Expected Output: False
Explanation: The start cell is completely blocked by obstacles, so no movement is possible.
Hints
- Think of each open cell as a node in a graph connected to its up, down, left, and right neighbors.
- Use BFS or DFS and keep track of visited cells so you do not process the same cell multiple times.