FastPrep
Problem · Graph

Grid Pathfinding with Obstacles (DFS)

● MediumRobloxPHONE SCREEN
See Roblox hiring insights

You are given a 2D grid of characters representing a board. Each cell is one of:

  • 'W' — a walk cell. From here the player moves 1 step to any of the four orthogonal neighbours.
  • 'J' — a jump cell. From here the player moves exactly 2 cells in any of the four orthogonal directions (skipping over the cell in between).
  • '#' — an obstacle. The player cannot stand on this cell.

The move type at each step is determined by the cell the player is currently on, not where they are moving to. A move is valid only if the landing cell is inside the grid and is not an obstacle. When jumping, the player may fly over an obstacle in the cell between — only the landing square must be non-obstacle.

You are also given a start and a target coordinate, both guaranteed to be inside the grid and on a non-obstacle cell.

Return true if the player can reach target from start under these rules, and false otherwise. The prompt specifically asks for a DFS: treat each non-obstacle cell as a node whose outgoing edges depend on whether it is 'W' (four 1-step neighbours) or 'J' (four 2-step neighbours), and recurse with a visited set to avoid cycles.

Follow-up. Return the minimum number of moves to reach target (or -1 if unreachable). Because every walk and every jump counts as one unit-weight move, switch to BFS: explore cells in layers of increasing distance, and the first time the target is reached the recorded distance is minimal.

Alternate canonical variant. A simpler reported form uses a grid of '.' (empty, walkable) and '#' (obstacle) cells with plain 1-step moves in the four orthogonal directions, and asks only whether end is reachable from start via DFS. The Walk/Jump version above generalizes it by making the step size cell-dependent.

Examples
01 · Example 1
grid = ["WWW", "W#W", "WWW"]
start = [0, 0]
target = [2, 2]
return = true
Every non-obstacle cell is a walk cell, so the player moves one step at a time. An L-shaped path around the obstacle at (1,1) reaches the target, e.g. (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2).
02 · Example 2
grid = ["JWW", "###", "WWW"]
start = [0, 0]
target = [2, 0]
return = true
Cell (0,0) is a jump cell, so the player jumps 2 cells down, flying over the obstacle at (1,0) and landing on the non-obstacle cell (2,0), which is the target. Only the landing square must be clear.
03 · Example 3
grid = ["WWWW", "####", "WWWW"]
start = [0, 0]
target = [2, 3]
return = false
Row 1 is a solid wall of obstacles. Walk cells only step 1, so the player can never cross from the top row to the bottom row, and the target is unreachable.
Constraints
  • 1 <= grid.length, grid[i].length <= 100
  • Each cell is 'W', 'J', or '#' (or, in the alternate variant, '.' or '#').
  • start and target are length-2 [row, col] pairs inside the grid, each on a non-obstacle cell.
  • 0 <= start[0], target[0] < grid.length and 0 <= start[1], target[1] < grid[0].length.
More Roblox problems
drafts saved locally
public boolean canReach(String[] grid, int[] start, int[] target) {
  // write your code here
}
grid["WWW", "W#W", "WWW"]
start[0, 0]
target[2, 2]
expectedtrue
sign in to submit