Extend a Maze Solver
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an existing codebase for a maze game and solver. The maze is represented as a 2D grid containing:
- `S`: start cell
- `T`: target cell
- `.`: open cell
- `#`: wall
Movement is allowed in the four cardinal directions.
Complete the following tasks progressively:
1. **Fix the existing implementation** so that the provided unit tests for basic maze traversal pass.
2. **Implement shortest-path search using BFS**. Add a function that returns the minimum number of moves from `S` to `T`, or `-1` if the target is unreachable.
3. **Add movement restrictions**. Update the move logic so that certain directional constraints are enforced during traversal, such as disallowing specific moves based on the previous move or the current cell's rules.
4. **Support keys and doors**. Extend the maze so that lowercase letters such as `a`, `b`, `c` represent keys, and uppercase letters such as `A`, `B`, `C` represent doors. A door may only be passed after collecting its matching key. The solver must still return the minimum number of moves required to reach `T`.
Your implementation should correctly track search state, handle revisits only when beneficial, and remain compatible with the existing test-driven codebase.
Overview: This question evaluates algorithmic problem-solving and software engineering skills, specifically graph traversal (BFS), state-space modeling for keys and doors, handling movement constraints, and debugging an existing codebase within the Coding & Algorithms domain.