Navigate a Maze Through a Next-Step API

Problem Statement

You are placed at an unknown starting position inside a 2D maze. You do not have direct access to the maze grid, dimensions, or layout. Instead, you interact with the environment strictly through a stateful MazeRunner interface.

Implement the function find_exit(runner: MazeRunner) -> list[str], which navigates the maze and returns an ordered list of move directions ('U', 'D', 'L', 'R') that leads from the starting cell to an exit cell. If no exit is reachable, return an empty list [].

MazeRunner Interface

class MazeRunner:
    def step(self, direction: str) -> str:
        """
        Attempts to move one cell in the given direction.
        direction: 'U' (up), 'D' (down), 'L' (left), or 'R' (right).
        
        Returns:
          - 'WALL': A wall blocked the move. Runner position does NOT change.
          - 'EMPTY': The move succeeded. Runner is now in the new cell.
          - 'EXIT': The move succeeded and the runner is now at an exit cell.
        """
        pass

    def is_exit(self) -> bool:
        """
        Returns True if the runner is currently on an exit cell, False otherwise.
        """
        pass

Constraints

• The maze is finite with at most 1,000 reachable empty cells.
• Valid directions are 'U', 'D', 'L', 'R'.
• Moving 'U' decreases the row coordinate (r - 1), 'D' increases row (r + 1), 'L' decreases column (c - 1), 'R' increases column (c + 1).
• The maze may contain cycles, dead ends, and disconnected regions.
• The starting position itself might already be an exit.

Examples

Example 1

# Maze layout (S = start, E = exit, # = wall, . = open):
# # # # #
# # S . #
# # # E #
# # # # #

# Execution:
runner.step('U') -> 'WALL'
runner.step('R') -> 'EMPTY'
runner.step('D') -> 'EXIT'

# Output:
['R', 'D']

Example 2

# Starting cell is already the exit
runner.is_exit() -> True

# Output:
[]

Edge Cases

• The runner starts directly on the exit (is_exit() returns True immediately).
• No exit exists in the reachable component (must backtrack fully and return []).
• Loops and corridors with multiple intersections.