Ранок після Геловіну#5832
Ви працюєте в парку розваг оператором будинку з привидами, де гості проходять через вузькі та темні коридори. Будинок славиться своїми живими привидами, які насправді є роботами, дистанційно керованими оператором, що ховаються в коридорах. Одного ранку ви виявили, що привиди не знаходяться на своїх місцях. Вчора було Геловін, і, вірите чи ні, паранормальні духи перемістили їх по коридорах вночі. Вам потрібно розставити їх на правильні позиції до приходу гостей. Ваш менеджер хоче знати, скільки часу займе відновлення розташування привидів.
У цій задачі вам потрібно написати програму, яка, маючи карту поверху будинку, знаходить мінімальну кількість кроків, щоб перемістити всіх привидів на позиції, де вони мають бути.
Поверх складається з матриці квадратних клітинок. Клітинка може бути або стіною, куди привиди не можуть рухатися, або коридором, де вони можуть.
На кожному кроці ви можете переміщати будь-яку кількість привидів одночасно. Кожен привид може залишитися на поточній клітинці або переміститися в одну з коридорних клітинок у своєму 4-сусідстві (тобто відразу ліворуч, праворуч, вгору або вниз), якщо привиди задовольняють наступним умовам:
Не більше одного привида займає одну позицію в кінці кроку.
Жодна пара привидів не обмінюється своїми позиціями один з одним за крок.
Наприклад, припустимо, що привиди розташовані, як показано на наступній (частковій) карті, де знак решітки ('#') представляє клітинку стіни, а 'a', 'b' і 'c' — привиди.
Наступні чотири карти показують єдині можливі позиції привидів після одного кроку.
Вхід складається з не більше ніж наборів даних, кожен з яких представляє карту поверху будинку. Формат набору даних наступний.
c_{11} c_{12} ... c_{1w}
c_{21} c_{22} ... c_{2w}
... ... ... ...
c_{h1} c_{h2} ... c_{hw}
, і у першому рядку є цілими числами, розділеними пробілом. і — це ширина і висота поверху будинку відповідно. — це кількість привидів. Вони задовольняють наступним обмеженням.
4 \le w \le 16, 4 \le h \le 16, 1 \le n \le 3
Наступні рядків по символів — це карта поверху. Кожен з c_{ij} може бути:
'#' представляє клітинку стіни,
малою літерою, що представляє коридорну клітинку, яка є початковою позицією привида,
великою літерою, що представляє коридорну клітинку, яка є позицією, де привид, що відповідає його малій літері, повинен бути, або
пробіл, що представляє коридорну клітинку, яка не є жодною з вищезазначених.
На кожній карті кожна з перших літер від 'a' і перших літер від 'A' з'являється один раз і тільки один раз. Найзовнішні клітинки карти є стінами; тобто всі символи першого і останнього рядків — це решітки; і перший і останній символи в кожному рядку також є решітками. Всі коридорні клітинки на карті з'єднані; тобто, маючи коридорну клітинку, ви можете дістатися до будь-якої іншої коридорної клітинки, слідуючи коридорним клітинкам у -сусідствах. Аналогічно, всі клітинки стін з'єднані. Будь-яка область 2 \times 2 на будь-якій карті має принаймні одну решітку. Ви можете припустити, що кожна карта має послідовність переміщень привидів, яка переміщує всіх привидів на їхні потрібні позиції.
Останній набір даних слідує за рядком, що містить три нулі, розділені пробілом.
Для кожного набору даних у вхідних даних потрібно вивести один рядок, що містить найменшу кількість кроків, щоб перемістити привидів на позиції, де вони мають бути. Рядок виводу не повинен містити зайвих символів, таких як пробіли.
Приклад 1