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