← 返回 meta 的题目列表Maze Solver with Keys and Doors (Grid BFS)
类型：online_judge
Coding: Shortest Path in a Maze with Keys and Doors
You are given a 2D grid grid. Start from S and reach E. Cells are:
S: start (unique)
E: exit (unique)
.: empty
#: wall
a-f: keys (up to 6 types)
A-F: doors, passable only if you have the corresponding lowercase key
You may move 4-directionally. Each move costs 1.
Task
Return the minimum number of steps from S to E, or -1 if impossible.
Input (stdin)
First line: m n
Next m lines: strings of length n
Output (stdout)
One integer: min steps or -1.
Constraints
1 <= m, n <= 100
Up to 6 keys (a-f)
Exactly one S and one E
Test cases
Example
Input
3 4
S..#
.aA.
...E
Output
5