Navigate unknown grid to locate target

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.