Navigate unknown grid to locate target
Overview
This question evaluates algorithmic problem-solving and spatial reasoning skills, particularly graph traversal, exploration in unknown environments, state encoding for relative coordinates, and reasoning about correctness.
You control a mouse in an unknown 2D maze. You do not know the maze dimensions or your absolute coordinates. The interface exposes move() → bool (attempts to move one step forward; returns false if blocked), turnLeft(), and turnRight(). A cell may contain cheese; calling atCheese() returns true iff the current cell has cheese. Design an algorithm that guarantees the mouse will locate the cheese if it exists, exploring the maze via relative coordinates and marking visited cells. Provide correctness arguments and complexity analysis.