Mysterious Dungeons#3623
The Kingdom of Aqua Canora Mystica is a land known for its mysterious dungeons filled with hidden treasures and challenging puzzles. One day, while exploring a deep dungeon, you finally discover the path to an ancient chamber rumored to contain a legendary artifact.
However, as you approach the artifact, a magical trap is triggered! Suddenly, strange carpets and large rocks appear throughout the dungeon, blocking your way to the exit. The rocks and carpets were magically created by the ancient protection spells left by the dungeon's builders. Every rock occupies one whole cell, and you cannot go through that cell. Each carpet also covers exactly one cell. Each rock is labeled by an uppercase letter, and each carpet by a lowercase letter. Some of the rocks and carpets may have the same label.
While trying to escape, you observe the following peculiar behavior: When you step onto a cell covered by a carpet, all rocks labeled with the corresponding uppercase letter (e.g., the rocks with for the carpets with ) disappear. After this, you may move onto the cells where those rocks were. However, if you step onto the same carpet cell again, or onto another carpet cell with the same label, the rocks reappear and block your way once more. To make the rocks disappear again, you must step onto the corresponding carpet cell again.
Can you escape the dungeon? If so, how quickly can you reach the exit? Your task is to write a program that determines whether you can escape the dungeon, and computes the minimum time required.
The input consists of several data sets. Each data set begins with a line containing two integers, and (3 \leq W, H \leq 30). In each of the following lines, there are characters, describing the map of the dungeon as a W \times H grid of square cells. Each character is one of the following:
denoting your current position,
denoting the exit of the dungeon,
a lowercase letter denoting a cell covered by a carpet with the label of that letter,
an uppercase letter denoting a cell occupied by a rock with the label of that letter,
\textbf{#} denoting a wall,
denoting an empty cell.
Every dungeon is surrounded by wall cells (\textbf{#}), and has exactly one cell and one cell. There can be up to eight distinct uppercase labels for the rocks and eight distinct lowercase labels for the carpets. You can move to one of the adjacent cells (up, down, left, or right) in one second. You cannot move to wall cells or rock cells. A line containing two zeros indicates the end of the input and should not be processed.
For each data set, output the minimum time required to move from the cell to the cell, in seconds, in one line. If you cannot exit, output .
Example 1