FastPrep
Problem · Matrix

Explore an Unknown Grid and Find a Path

Learn this problem
● MediumLinkedIn logoLinkedInFULLTIMEONSITE INTERVIEW

Problem statement

A robot starts in an unexplored rectangular area. For this deterministic adapter, hiddenMap contains the environment: . is an open cell and # is a wall. The robot starts at start = [row, column], knows the target coordinate, and may inspect the four orthogonal neighbors of any cell it has already explored. It may also relocate to any previously explored open cell before continuing exploration.

Return a shortest open-cell path from start to target, including both endpoints. If several shortest paths exist, choose the lexicographically smallest coordinate sequence when coordinates are compared as [row, column]. Return an empty array when the target cannot be reached.

This finite adapter preserves the reported exploration and relocation state transitions; the hidden matrix supplies deterministic sensor outcomes for the judge.

Function

findExploredPath(hiddenMap: String[], start: int[], target: int[]) → int[][]

Examples

Example 1

hiddenMap = ["...",".#.","..."]start = [0,0]target = [2,2]return = [[0,0],[0,1],[0,2],[1,2],[2,2]]

Two shortest paths have four moves. The path beginning with [0,1] is lexicographically smaller than the one beginning with [1,0].

Example 2

hiddenMap = [".#.","###",".#."]start = [0,0]target = [2,2]return = []

Walls separate the target from the start.

Constraints

  • 1 <= hiddenMap.length, hiddenMap[i].length <= 500.
  • All rows have equal length and contain only . and #.
  • start and target identify open cells.
  • The robot explores only up, down, left, and right neighbors.

More LinkedIn problems

drafts saved locally
public int[][] findExploredPath(String[] hiddenMap, int[] start, int[] target) {
    // Write your code here.
}
hiddenMap["...",".#.","..."]
start[0,0]
target[2,2]
expected[[0,0],[0,1],[0,2],[1,2],[2,2]]
checking account