We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Path in a Hidden Grid

Number: 1931

Difficulty: Medium

Paid? Yes

Companies: Meta, Bloomberg

Problem Description

You are given a hidden grid where cells can be empty, blocked, or marked as a target. The grid is unknown in size and layout. You control a robot via an interactive GridMaster interface that can check if a move in one of the four directions (up, down, left, right) is possible, actually move the robot, and tell if the current cell is the target. Starting from an unknown starting cell (guaranteed empty) you need to find the shortest path to the target cell (if one exists) using the allowed operations. If no valid path exists, return -1.

Key Insights

  • Since the grid is hidden and unknown, you must explore it using DFS (Depth First Search) while backtracking.
  • Map the visited cells with relative coordinates starting from (0, 0) for the starting cell.
  • Record the status (empty or target) for each accessible cell during exploration.
  • After mapping the grid, use BFS (Breadth First Search) on the discovered grid to find the shortest path.
  • Backtracking is critical: after a move, always reverse the move to return to the previous state.

Space and Time Complexity

Time Complexity:

  • The DFS exploration traverses every reachable cell once. In the worst-case, this is O(m*n).
  • The subsequent BFS over the mapped grid is also O(m*n). Space Complexity:
  • O(m*n) for the mapping of the grid and the BFS queue.

Solution

We solve this problem in two phases:

  1. DFS Exploration:
    Use DFS to explore the grid from the start. For each accessible cell, record its relative coordinates and whether it is the target. Use the API calls of GridMaster to determine valid moves. Since moving is stateful, after moving in one direction, recursively perform DFS and then backtrack by performing the opposite move to return to the previous location.

  2. BFS to Determine Shortest Path:
    Once the grid is mapped, perform a BFS starting from the initial position (0,0) in the mapped grid. Calculate the minimum number of moves required to reach the target cell if it exists. If the BFS completes without finding the target, return -1.

Key data structures:

  • A dictionary (or map) to store visited cell coordinates and their state (empty or target).
  • A list/queue for BFS to compute the shortest path from the starting cell to the target cell.

Code Solutions

# Python solution for Shortest Path in a Hidden Grid
class Solution:
    # The main function to find the shortest path using GridMaster
    def findShortestPath(self, master: 'GridMaster') -> int:
        # Mapping of directions to row, column changes
        directions = {
            'U': (-1, 0),
            'D': (1, 0),
            'L': (0, -1),
            'R': (0, 1)
        }
        # Opposite directions for backtracking
        opposite = {
            'U': 'D',
            'D': 'U',
            'L': 'R',
            'R': 'L'
        }
        # Dictionary to record explored cells
        grid = {}  # key: (r, c), value: cell status (1 for empty, 2 for target)
        
        # DFS exploration function
        def dfs(r: int, c: int):
            # Mark current cell as empty, or as target if found
            grid[(r, c)] = 2 if master.isTarget() else 1
            # Explore all four directions
            for d in directions:
                dr, dc = directions[d]
                new_r, new_c = r + dr, c + dc
                # Skip if this cell is already visited
                if (new_r, new_c) in grid:
                    continue
                # Check if the robot can move in this direction
                if master.canMove(d):
                    # Move the robot in the chosen direction
                    master.move(d)
                    # Recursively explore the new cell
                    dfs(new_r, new_c)
                    # Backtracking to the previous cell
                    master.move(opposite[d])
        
        # Start DFS from the starting cell at coordinate (0,0)
        dfs(0, 0)
        
        # BFS to find the shortest path from (0,0) to target
        from collections import deque
        queue = deque()
        # Start from the origin with initial distance 0
        queue.append(((0, 0), 0))
        visited = set()
        visited.add((0, 0))
        
        while queue:
            (r, c), dist = queue.popleft()
            # Check if this cell is the target
            if grid[(r, c)] == 2:
                return dist
            # Try all possible moves
            for d in directions:
                dr, dc = directions[d]
                new_r, new_c = r + dr, c + dc
                if (new_r, new_c) in grid and (new_r, new_c) not in visited:
                    visited.add((new_r, new_c))
                    queue.append(((new_r, new_c), dist + 1))
        return -1  # target not reachable
← Back to All Questions