Головоломка с движущимися блоками
В головоломках с движущимися блоками мы многократно перемещаем части (блоки) на свободные места внутри рамки, чтобы достичь целевого расположения.
Создатель головоломок разработал новую задачу, объединив идеи головоломок с движущимися блоками и лабиринтов. Головоломка играется в прямоугольной рамке, разделенной на единичные квадраты. Некоторые из них заняты препятствиями. В рамке размещены несколько частей: одна 2×2 королевская часть и некоторое количество 1×1 пешек. Ровно два 1×1 квадрата остаются свободными. Если пешка находится рядом с открытым квадратом, её можно переместить туда. Если целая грань королевской части прилегает к двум открытым квадратам, её также можно переместить. Перемещать препятствия нельзя. Начиная с заданного начального расположения, цель головоломки - переместить королевскую часть в верхний левый угол рамки.
Следующая иллюстрация показывает начальное расположение четвертого набора данных из примера ввода.
Рисунок 1: Четвертый набор данных из примера ввода.
Ваша задача - написать программу, которая вычисляет минимальное количество ходов для решения головоломки из заданного расположения частей. Один ход означает перемещение либо королевской, либо пешечной части на соседнюю позицию.
Входные данные
Входные данные состоят из последовательности наборов данных. Первая строка каждого набора данных содержит два целых числа H и W, разделенных пробелом, где H и W - высота и ширина рамки. Следующие H строк, каждая из которых состоит из W символов, обозначают начальное расположение частей. В этих H строках 'X', 'o', '*', и '.' обозначают часть королевской части, пешку, препятствие и открытый квадрат соответственно. В этих H строках нет других символов. Вы можете предположить, что 3 ≤ H ≤ 50 и 3 ≤ W ≤ 50.
Строка, содержащая два нуля, разделенных пробелом, указывает на конец ввода.
Выходные данные
Для каждого набора данных выведите строку, содержащую минимальное количество ходов, необходимых для перемещения королевской части в верхний левый угол. Если это невозможно, выведите -1.