Таємничі підземелля#3623
Королівство Aqua Canora Mystica відоме своїми таємничими підземеллями, наповненими прихованими скарбами та складними головоломками. Одного дня, досліджуючи глибоке підземелля, ви нарешті знаходите шлях до давньої зали, про яку ходять чутки, що в ній зберігається легендарний артефакт.
Проте, як тільки ви наближаєтесь до артефакта, спрацьовує магічна пастка! Раптово по всьому підземеллю з'являються дивні килими та великі камені, перегороджуючи дорогу до виходу. Камені й килими були магічно створені давніми захисними закляттями, що залишили творці підземелля. Кожен камінь займає одну цілу клітинку, і ви не можете пройти через цю клітинку. Кожен килим теж покриває рівно одну клітинку. Кожен камінь позначено великою літерою, а кожен килим — маленькою літерою. Деякі камені й килими можуть мати однакові позначення.
Під час втечі ви помічаєте таку особливість: якщо ви ступаєте на клітинку, покриту килимом, зникають усі камені з відповідною великою літерою (наприклад, камені з для килимів з ). Після цього ви можете проходити через клітинки, де були ці камені. Однак, якщо ви знову ступите на цей самий килим або на інший килим з такою ж позначкою, камені знову з'являються і блокують шлях. Щоб камені знову зникли, потрібно знову наступити на відповідний килим.
Чи зможете ви вибратися з підземелля? Якщо так, то як швидко? Ваше завдання — написати програму, яка визначає, чи можливо втекти з підземелля, і знаходить мінімальний час, необхідний для цього.
Вхід складається з кількох наборів даних. Кожен набір починається рядком із двох цілих чисел і (3 \leq W, H \leq 30). У кожному з наступних рядків знаходиться по символів — це карта підземелля у вигляді сітки W \times H. Кожен символ — це один із:
— ваша поточна позиція,
— вихід з підземелля,
мала літера — клітинка, покрита килимом з міткою цієї літери,
велика літера — клітинка з каменем, позначеним цією літерою,
\textbf{#} — стіна,
— порожня клітинка.
Кожне підземелля оточене клітинками-стінами (\textbf{#}) і має рівно одну клітинку та одну клітинку . Може бути до восьми різних великих літер для каменів і до восьми різних малих літер для килимів. Ви можете переміщатися за одну секунду на одну із сусідніх клітинок (вгору, вниз, ліворуч або праворуч). Ви не можете рухатися на клітинки зі стінами або камінням. Рядок із двома нулями позначає кінець вводу і не обробляється.
Для кожного набору даних виведіть в одному рядку мінімальний час (у секундах), необхідний, щоб дійти від клітинки до клітинки . Якщо вийти неможливо, виведіть .
Приклад 1