Головоломка з ковзаючими блоками
У головоломках зі зсувними блоками ми переміщуємо частини (блоки) до відкритих місць у рамці, щоб досягти цільового розташування частин.
Творець головоломок розробив нову головоломку, поєднавши ідеї головоломок зі зсувними блоками та лабіринтів. Гра відбувається в прямокутній рамці, розділеній на одиничні квадрати. Деякі квадрати зайняті перешкодами. У рамці розміщено кілька частин: одна частина короля розміром 2×2 та кілька частин пішаків розміром 1×1. Точно два 1×1 квадрати залишаються відкритими. Якщо частина пішака знаходиться поруч з відкритим квадратом, ми можемо зсунути її туди. Якщо цілий край частини короля знаходиться поруч з двома відкритими квадратами, ми можемо зсунути частину короля. Перешкоди переміщати не можна. Починаючи з даного початкового розташування, мета головоломки - перемістити частину короля у верхній лівий кут рамки.
Наступна ілюстрація показує початкове розташування четвертого набору даних з прикладу введення.
Фігура 1: Четвертий набір даних з прикладу введення.
Ваше завдання - написати програму, яка обчислює мінімальну кількість ходів для розв'язання головоломки з даного розташування частин. Один хід означає зсув частини короля або пішака на сусідню позицію.
Вхідні дані
Вхід складається з послідовності наборів даних. Перша строка кожного набору даних містить два цілі числа H та W, розділені пробілом, де H та W - це висота та ширина рамки. Наступні H рядків, кожен з яких складається з W символів, позначають початкове розташування частин. У цих H рядках 'X', 'o', '*', та '.' позначають частину короля, частину пішака, перешкоду та відкритий квадрат відповідно. Інших символів у цих H рядках немає. Ви можете припустити, що 3 ≤ H ≤ 50 та 3 ≤ W ≤ 50.
Рядок, що містить два нулі, розділені пробілом, вказує на кінець введення.
Вихідні дані
Для кожного набору даних виведіть рядок, що містить мінімальну кількість ходів, необхідних для переміщення частини короля у верхній лівий кут. Якщо це неможливо, виведіть -1.