Раскрашенный куб
Как только кольцо всевластия оказалось у Фродо, Гэндальф сразу отправился за советом к главе своего ордена, Саруману. Саруман не согласился с мнением Гэндальфа о том, что кольцо нужно уничтожить. Он решил, что не может просто так отпустить Гэндальфа и помочь Фродо, поэтому запер его в самой высокой комнате своей мрачной башни в Изенгарде. Чтобы занять Гэндальфа, он установил в комнате единственную дверь, которую можно было открыть, только решив загадку.
После недолгих поисков выхода из комнаты Гэндальф заметил весьма необычный замок на двери, которая, казалось, вела на крышу башни. Замок представлял собой стандартный шестигранный куб без каких-либо отметок на его поверхностях. Он был помещен на сетку размером m×n. На сетке было ровно шесть квадратов с краской. Гэндальф заметил, что когда он перекатывал пустую грань куба на квадрат с краской, отметки переносились с сетки на грань куба. Когда куб перекатывался на квадрат, где не было краски, а контактная поверхность куба имела отметку, отметка переносилась с куба на сетку. Если куб перекатывался на квадрат сетки, на котором была отметка, и контактная поверхность куба также имела какую-либо отметку, то ничего не происходило.
Гэндальф предположил, что открыть дверь на крышу можно только в том случае, если куб будет перекатан последовательностью ходов к целевому квадрату так, чтобы все отметки с сетки были перенесены на куб. Более того, чтобы выбраться из ловушки Сарумана, он (правильно) догадался, что ему нужно сделать это минимальным количеством ходов.
Дано начальное расположение краски на квадратах, начальное положение куба и желаемое целевое положение, какое минимальное количество ходов должен сделать Гэндальф, чтобы привести куб в целевое состояние с краской на всех его сторонах?
Для первого примера (см. ниже) примером решения будет последовательность: вниз, вправо, вправо, вверх, вправо, вправо, вниз, влево, вправо, влево.
Входные данные
Входной файл будет содержать несколько тестовых случаев. Каждый тестовый случай будет состоять из сетки символов размером m×n, где m и n находятся в пределах от 2 до 20. В каждом тестовом случае пустые пространства будут описаны символом '.', окрашенные квадраты — символом 'P', недопустимые квадраты — символом '#', начальное положение куба — символом 'C', а целевой квадрат — символом 'G'. Всегда будет ровно 6 'P', ровно один 'C', ровно один 'G' и не более 12 '.'. Входные тестовые случаи будут разделены одной пустой строкой. Ввод будет завершен концом файла.
Выходные данные
Для каждого входного тестового случая выведите минимальное количество ходов, необходимых для достижения целевого состояния. Если достичь этого состояния невозможно, выведите -1.