Navigate unknown maze to find target

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.

Navigate an Unknown Maze to Find the Cheese

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).

Hints

1. 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.
2. 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.
3. 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.
4. 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.