Комната с кубиками
Вы играете в популярную видеоигру, известную своей глубокой историей и увлекательными головоломками. В игре вы оказались заперты в таинственном доме в одиночестве, и помощи ждать неоткуда, поэтому вам нужно выбраться самостоятельно. Однако почти в каждой комнате дома есть головоломки, и вы не сможете перейти в соседнюю комнату, пока не решите их.
Одна из головоломок, с которой вы столкнулись, следующая. В комнате находится устройство, напоминающее игральную кость, лежащее на столе в центре. На стене написана инструкция:
"Этот куб — пульт дистанционного управления, с помощью которого вы можете манипулировать удаленной комнатой, называемой Комнатой Куба. Комната имеет кубическую форму, и её поверхности состоят из 3x3 единичных квадратов. Некоторые из этих квадратов имеют отверстия, достаточно большие, чтобы вы могли пройти через них. Вы можете вращать этот куб так, чтобы в процессе вращения хотя бы одно ребро всегда касалось стола, то есть в 4 направлениях. Вращение этого куба влияет на удаленную комнату аналогичным образом, и позиции отверстий в комнате меняются. Чтобы пройти через комнату, отверстия должны быть хотя бы в одном из нижних трех квадратов на передней и задней стороне комнаты."
Вы видите текущие позиции отверстий на мониторе. Прежде чем отправиться в Комнату Куба, вы должны повернуть куб так, чтобы можно было пройти через комнату. Однако вы знаете, что вращение комнаты занимает некоторое время, и у вас его не так много, поэтому необходимо минимизировать количество вращений. Сколько вращений вам нужно сделать, чтобы пройти через Комнату Куба?
Входные данные
Входные данные состоят из нескольких наборов. Каждый набор содержит 6 таблиц размером 3×3 символов, которые описывают начальное положение отверстий на каждой стороне. Каждый символ — это либо '*', либо '.'. Отверстие обозначается символом '*'. Порядок, в котором появляются шесть сторон, следующий: передняя, правая, задняя, левая, верхняя, нижняя. Порядок и ориентация описаны на этой развертке:
Рисунок 1: Комната Куба
Рисунок 2: доступные вращения куба
После каждого набора данных идет пустая строка. Конец ввода обозначается одиночным символом '#'.
Выходные данные
Выведите минимальное количество вращений, необходимых для каждого набора данных, в отдельной строке. Вы можете предположить, что все наборы данных имеют решение.