Задачи заочного тура личного первенства

Эта головоломка состоит из двух колес. Оба колеса могут вращаться по часовой и против часовой стрелки. Они содержат 21 цветные части, 10 из которых – округленные треугольники и 11 из которых – прямоугольные сепараторы. Рисунок 1 показывает конечное положение каждой части. Заметьте, чтобы выполнить одно вращение вы должны повернуть колесо так, чтобы продвинулся и треугольник и сепаратор.

Рисунок 1. Конечное состояние головоломки

Ваша работа – написать программу, которая читает состояние головоломки и печатает минимальную последовательность перемещений, требуемых, чтобы достигнуть конечного состояния. Мы используем следующие целые значения, чтобы кодировать каждый тип фрагмента:

0 серый сепаратор

1 желтый треугольник

2 желтый сепаратор

3 синий треугольник

4 синий сепаратор

5 фиолетовый треугольник

6 фиолетовый сепаратор

7 зеленый треугольник

8 зеленый сепаратор

9 красный треугольник

10 красный сепаратор

Состояние головоломки может быть описана, используя 24 целых числа, первые 12, чтобы описать левое колесо, и последние 12 – для правого колеса. Первое целое число представляет сепаратор правой нижней части левого колеса, и следующие одиннадцать целых чисел описывают левое колесо по часовой стрелке. Тринадцатое целое число представляет сепаратор левой нижней части правого колеса, и следующие одиннадцать целых чисел описывают правое колесо против часовой стрелки.

Конечное состояние следовательно кодируется так:

0 3 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1

Если, например, мы вращаем левое колесо по часовой стрелке на один шаг из конечного состояние (как показано на рисунке 2), состояние головоломки кодируется так:

2 1 0 3 4 3 0 5 6 5 0 1 0 7 8 7 0 9 10 9 0 5 0 1

Рисунок 2. Состояние головоломки после поворота левого колеса на один шаг из конечного состояния.

Ввод для вашей программы состоит из отдельных задач. Первая линия ввода будет содержать целое число n – число задач. Затем следует n строк, каждая содержит 24 целых числа, разделенных пробелом, описывающие начальное состояние головоломки, как объяснено выше.

Для каждого состояния ваша программа должна вывести одна строку с только одним числом, представляющим решение. Каждое перемещение кодируется, используя один разряд от 1 до 4 следующим способом:

1 – поворот левого колеса по часовой стрелке

2 – поворот правого колеса по часовой стрелке

3 – поворот левого колеса против часовой стрелки

4 – поворот правого колеса против часовой стрелки

Никаких пробелов не должно быть напечатано между цифрами. Так как несколько решений может быть найдено, вы должны печатать решение, которое кодируется как самый маленькое число. Решение никогда не будет требовать больше чем 16 перемещений.

Если решение за 16 перемещений не найдено, вы должны напечатать "NO SOLUTION WAS FOUND IN 16 STEPS". Если при вводе встретится конечное состояние, вы должны напечатать "PUZZLE ALREADY SOLVED".

3
0 3 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1
0 3 4 5 0 3 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1
0 9 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 3 0 1 2 1

PUZZLE ALREADY SOLVED
1434332334332323
NO SOLUTION WAS FOUND IN 16 STEPS