AI Coding: Maze shortest path with keys/doors (BFS pitfalls)

You are given a 2D grid maze (character matrix): S: start E: exit #: wall (blocked) .: empty cell a-f: keys (once picked up, kept forever) A-F: doors (can pass only if you have the matching lowercase key) Starting from S, find the minimum number of steps to reach E (each move to an adjacent cell costs 1). If unreachable, output -1. Moves allowed: up/down/left/right by 1 cell. Input (stdin): First line: two integers m n Next m lines: a string of length n describing the grid Output (stdout): One integer: the minimum steps, or -1 if not reachable Constraints: 1 <= m, n <= 200 Up to 6 key types (a-f) Common interview follow-up: without a visited set BFS can revisit states indefinitely; visited must be on (row, col, keyMask). Example Input 3 3 S.. ##. ..E Output 4