Navigate unknown maze to find target
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an exploration interface for an unknown 2D maze that exposes only local actions (e.g., move(up/down/left/right) -> bool indicating success, position() -> (r,c), and atCheese() -> bool). Starting from an initial cell, design an algorithm to find the cheese with the fewest steps if it is reachable, minimizing redundant moves. You may adapt/override the interface to enable breadth-first exploration on the fly (e.g., by building a discovered map and backtracking). Specify visited-state representation, frontier management, termination conditions, and complexity in terms of reachable cells. Follow-up: Propose unit tests, including obstacles at start, multiple cheeses, unreachable cheese, loops, unknown bounds, and large open areas.
Quick Answer: This question evaluates understanding of graph traversal and exploration algorithms, representation of visited state and frontiers, path optimality, and complexity analysis in an environment constrained to local actions.
A mouse explores an unknown 2D maze and must reach the cheese using the fewest moves. The maze is modeled as a grid of integers:
- `0` — an open cell the mouse can stand on
- `1` — a wall / obstacle the mouse cannot enter
- `2` — the cell containing the cheese (the target)
The mouse starts at cell `start = (r, c)` and may move one step at a time **up, down, left, or right** (no diagonals). Implement breadth-first exploration of the unknown maze and return the **minimum number of moves** needed to reach a cheese cell.
Return `-1` if the start is out of bounds, the start cell is a wall, or no cheese cell is reachable from the start. If the mouse already starts on the cheese, the answer is `0`.
This is the executable core of the classic "mouse finds cheese" / unknown-maze interface problem: BFS guarantees the first time the target is dequeued (or discovered) it is reached via a shortest path, so redundant moves are minimized. The `visited` grid is the visited-state representation, the FIFO queue is the frontier, and termination occurs when the cheese is found or the frontier empties.
**Example 1**
```
grid = [[0, 0, 0],
[1, 1, 0],
[0, 0, 2]]
start = (0, 0)
```
The direct path down is blocked by the wall row, so the mouse goes right along the top row then down the right column: (0,0)->(0,1)->(0,2)->(1,2)->(2,2). That is **4** moves.
**Example 2**
```
grid = [[0, 1, 2],
[1, 1, 1],
[0, 0, 0]]
start = (0, 0)
```
The cheese at (0,2) is fully walled off from the start, so the answer is **-1**.
Constraints
- 1 <= R, C <= 1000 (R = number of rows, C = number of columns).
- Each cell value is one of: 0 (open), 1 (wall), or 2 (cheese).
- There is at most one cheese cell relevant to the answer; if several exist, return the distance to the nearest reachable one.
- 0 <= start[0] < R and 0 <= start[1] < C for valid input, but the function must also return -1 for an out-of-bounds or wall start.
- Movement is restricted to the four orthogonal directions (up, down, left, right).
Examples
Input: ([[0, 0, 0], [1, 1, 0], [0, 0, 2]], (0, 0))
Expected Output: 4
Explanation: The wall row forces a detour: (0,0)->(0,1)->(0,2)->(1,2)->(2,2), which is 4 moves — the shortest path around the obstacle.
Input: ([[0, 1, 2], [0, 1, 0], [0, 0, 0]], (0, 0))
Expected Output: 6
Explanation: A vertical wall splits the grid, so the mouse must go all the way down the left column, across the bottom row, and up the right column to reach the cheese — 6 moves.
Hints
- BFS, not DFS: BFS explores cells in order of increasing distance, so the first time you reach the cheese you have used the fewest possible moves. DFS can find a path but not necessarily the shortest one.
- Mark a cell visited the moment you enqueue it (not when you dequeue it). Otherwise the same cell can be pushed multiple times, inflating the queue and risking redundant exploration.
- Handle the degenerate cases up front: start out of bounds, start on a wall, and start already on the cheese (answer 0). Walls (value 1) must never be entered or enqueued.
- Track distance by storing it alongside each queued cell (or by processing the queue one 'level' at a time). When the frontier empties without finding a 2, the cheese is unreachable — return -1.