Haunted House Key Collector

Problem Description

Imagine a haunted mansion represented as a 2D grid. Each cell in the grid can be one of the following:

• . — an empty room you can walk through
• # — a wall that you cannot pass through
• @ — your starting position (appears exactly once)
• $ — the exit you need to reach (appears exactly once)
• Lowercase letters (a to f) — keys that can be picked up
• Uppercase letters (A to F) — locked doors that can only be passed if you have the matching key

You can move one step at a time in the four cardinal directions (up, down, left, right). When you move onto a cell with a key, you automatically pick it up and can then open the corresponding door (i.e., if you pick up key a, all doors A become passable).

Your goal is to determine the minimum number of steps required to go from the starting position @ to the exit $, collecting keys as necessary along the way to open doors. If it is impossible to reach the exit, your program should return -1.

Input

• A 2D grid of characters representing the haunted mansion.

Output

• An integer representing the minimum number of steps required to reach the exit, or -1 if the exit cannot be reached.

Example

For the grid:

@.a#
###A
b.$B

A valid solution might determine the minimum steps to collect key a, open door A, pick up key b, open door B, and finally reach the exit $.

Notes

• There might be multiple keys and doors. Keys and their corresponding doors will always be paired by letter (lowercase for keys and uppercase for doors).
• Some keys or doors might not be necessary to reach the exit.
• Design your solution to efficiently handle larger grids.