Keycards in the Night Vault

A security guard walks a vault floor plan grid, a list of equal-length strings:

• 'S' is the guard's start (exactly one), 'X' is the exit (exactly one);
• '.' is open floor and '#' is a wall;
• a lowercase letter 'a' to 'f' is a keycard; stepping onto it picks it up, and a keycard is kept forever (it is never used up). The same letter may appear on several cells;
• an uppercase letter 'A' to 'F' is a locked door; the guard may step onto it only while holding the keycard with the matching lowercase letter.

Each move goes one cell up, down, left or right and costs one step. Return the fewest steps needed to reach 'X', or -1 if the exit cannot be reached. Cells may be visited any number of times.

Examples

Input:  grid = ["S.a",
                "##A",
                "X.."]
Output: 6
Explanation: right twice to the keycard, down through door A, down again, then left twice:
             (0,0) (0,1) (0,2) (1,2) (2,2) (2,1) (2,0) is 6 steps.

Input:  grid = ["SAX"]
Output: -1
Explanation: there is no keycard a anywhere, so door A never opens.

Input:  grid = ["Sb#X",
                ".#.B",
                "a.A."]
Output: 9
Explanation: fetch b first (1 step), come back and walk down to a (3 more), then go through A and
             B to the exit (5 more).

Constraints

• 1 <= rows, cols <= 40, rows * cols >= 2.
• Only the letters a-f and A-F appear as keycards and doors; a door with no matching keycard in the grid can never be opened.

Goals

• Recognise that position alone is not a valid BFS state
• Encode the set of collected keycards as a bitmask
• Run BFS over (cell, keycards held) pairs