Ранок після Геловіну
Ви працюєте в парку розваг оператором будинку з привидами, де гості проходять через вузькі та темні коридори. Будинок славиться своїми живими привидами, які насправді є роботами, дистанційно керованими оператором, що ховаються в коридорах. Одного ранку ви виявили, що привиди не знаходяться на своїх місцях. Вчора було Хелловін, і, вірите чи ні, паранормальні духи перемістили їх по коридорах вночі. Вам потрібно повернути їх на правильні позиції до приходу гостей. Ваш менеджер хоче знати, скільки часу займе відновлення привидів.
У цій задачі вам потрібно написати програму, яка, маючи карту поверху будинку, знаходить мінімальну кількість кроків, щоб перемістити всіх привидів на їхні початкові позиції.
Поверх складається з матриці квадратних клітинок. Клітинка може бути або стіною, куди привиди не можуть рухатися, або коридором, де вони можуть.
На кожному кроці ви можете переміщати будь-яку кількість привидів одночасно. Кожен привид може залишитися на поточній клітинці або переміститися в одну з коридорних клітинок у своєму 4-сусідстві (тобто відразу ліворуч, праворуч, вгору або вниз), якщо привиди задовольняють наступним умовам:
Не більше одного привида займає одну позицію в кінці кроку.
Жодна пара привидів не обмінюється своїми позиціями один з одним за крок.
Наприклад, припустимо, що привиди розташовані, як показано на наступній (частковій) карті, де знак решітки ('#') представляє клітинку стіни, а 'a', 'b' і 'c' — привиди.
Наступні чотири карти показують єдині можливі позиції привидів після одного кроку.
Вхідні дані
Вхід складається з не більше ніж 10 наборів даних, кожен з яких представляє карту поверху будинку. Формат набору даних наступний.
w h n
c_11 c_12 ... c_1w
c_21 c_22 ... c_2w
... ... ... ...
c_{h1 }c_h2 ... c_hw
w, h і n у першому рядку є цілими числами, розділеними пробілом. w і h — це ширина і висота поверху будинку відповідно. n — це кількість привидів. Вони задовольняють наступним обмеженням.
4 ≤ w ≤ 16, 4 ≤ h ≤ 16, 1 ≤ n ≤ 3
Наступні h рядків по w символів — це карта поверху. Кожен з c_ij може бути:
'#' представляє клітинку стіни,
малою літерою, що представляє коридорну клітинку, яка є початковою позицією привида,
a_n великою літерою, що представляє коридорну клітинку, яка є позицією, де привид, що відповідає його малій літері, повинен бути, або
пробіл, що представляє коридорну клітинку, яка не є жодною з вищезазначених.
На кожній карті кожна з перших n літер від a і перших n літер від A з'являється один раз і тільки один раз. Найзовнішні клітинки карти є стінами; тобто всі символи першого і останнього рядків — це решітки; і перший і останній символи в кожному рядку також є решітками. Всі коридорні клітинки на карті з'єднані; тобто, маючи коридорну клітинку, ви можете дістатися до будь-якої іншої коридорної клітинки, слідуючи коридорним клітинкам у 4-сусідствах. Аналогічно, всі клітинки стін з'єднані. Будь-яка 2×2 область на будь-якій карті має принаймні одну решітку. Ви можете припустити, що кожна карта має послідовність переміщень привидів, яка відновлює всіх привидів на позиції, де вони повинні бути.
Останній набір даних слідує за рядком, що містить три нулі, розділені пробілом.
Вихідні дані
Для кожного набору даних у вхідних даних потрібно вивести один рядок, що містить найменшу кількість кроків, щоб відновити привидів на позиції, де вони повинні бути. Рядок виводу не повинен містити зайвих символів, таких як пробіли.