Practice/Meta/Help Mouse Find the Cheese

Help Mouse Find the Cheese

CodingMust

Problem

You are controlling a robot navigating through a grid to locate a target. However, you have very limited control over the robot - you can only interact with it through a constrained API provided by a Robot class.

The Robot class provides only these methods:

• move(direction: str) -> bool: Attempts to move the robot in the specified direction ("UP", "DOWN", "LEFT", or "RIGHT"). Returns True if the move was successful (no wall or boundary), and the robot's position changes. Returns False if the move is blocked, and the robot stays in place.
• atTarget() -> bool: Returns True if the robot is currently positioned at the target location, False otherwise.

Your task is to implement a function that navigates the robot to find the target. You cannot access the grid directly, query the robot's position, or know the grid's dimensions in advance. You must rely solely on the provided API methods.

The grid is guaranteed to have exactly one target, and it is always reachable from the robot's starting position.

Requirements

1. Navigate the robot to the target using only move() and atTarget() methods
2. Return True once the robot reaches the target
3. Handle grids of any size and shape with arbitrary wall configurations
4. Implement a search strategy that explores the grid systematically
5. Avoid infinite loops by tracking visited positions

Constraints

• Grid dimensions: 1 ≤ rows, cols ≤ 100
• You cannot access the grid structure directly
• You cannot query the robot's current position explicitly
• The target is always reachable from the starting position
• Expected time complexity: O(rows × cols) in worst case
• Expected space complexity: O(rows × cols) for tracking visited positions

Examples

Example 1:

` Grid visualization (M = robot, C = target, # = wall, . = empty): M . . . . . . . C

Starting position: (0, 0) Target position: (2, 2)

Output: True Explanation: Robot explores the grid using DFS/BFS and successfully reaches the target. `

Example 2:

` Grid visualization: M . # . . . # .

. . .

. . . C

Starting position: (0, 0) Target position: (3, 3) Walls block direct diagonal path

Output: True Explanation: Robot must navigate around walls, exploring multiple paths until it finds the target. `

Example 3:

` Grid visualization: M . . . . . . . . C

Starting position: (0, 0) Target position: (0, 9)

Output: True Explanation: Robot moves right through the corridor until reaching the target. `