← 返回 pinterest 的题目列表Escape Room (Shortest Escape Path in a Room Grid)
类型：online_judge
Problem: Escape Room (Shortest Escape Path in a Room Grid)
You are given a 2D grid representing an “escape room map”. You start from S and want to reach the exit E in the minimum number of steps, following the rules below.
Cell types
Each cell is a character:
S: Start (appears once)
E: Exit (appears once)
.: Free cell
#: Wall (blocked)
Lowercase a-z: Keys; stepping on the cell picks it up
Uppercase A-Z: Doors; you may enter only if you already have the corresponding key (e.g., a for A)
Movement
In one step, you may move to one of the 4 neighboring cells (up/down/left/right), no diagonals, as long as the target cell is enterable:
You cannot enter #
To enter a door A-Z, you must have its key
Keys, once collected, are kept forever (not consumed).
Task
Return the minimum number of steps from S to E. If it is impossible, return -1.
Constraints (for solution design)
1 <= m, n <= 30
Number of distinct keys k <= 10
Input/Output
Input (stdin)
First line: two integers m n
Next m lines: each a string of length n
Output (stdout)
One integer: the minimum steps, or -1
Example 1
Input:
3 4
S..#
.aA.
...E
Output:
5
Example 2
Input:
2 3
S#E
...
Output:
4
Example
Input
3 4
S..#
.aA.
...E
Output
5