printРабочее место участника

printЗадачи

1756. Головоломка

Ограничения: время – 4s/8s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (2)

Всем известна игра 15, где надо выстроить изначально неупорядоченную последовательность чисел, перемещая фишки с нанесёнными числами от 1 до 15 в квадрате 4x4. На основе данной игры была разработана другая – поле в ней лишь 4x2 клетки, на поле 7 фишек, но на фишках изображены буквы латинского алфавита и арабские цифры (на каждой фишке – один символ, но на разных фишках могут быть одинаковые символы). Цель игры прежняя – упорядочить в соответствии с образцом стартовую расстановку фишек за минимальное количество ходов.
Свободная клетка обозначается специальным символом # и используется для перемещения фишек по полю. Перемещать фишки на свободную клетку разрешается из соседних клеток, имеющих общую грань со свободной. Например, на рисунке более правый символ 0 можно переместить вниз на свободную клетку, тогда 0 будет в нижней клетке, а пустой станет верхняя клетка, либо в свободную клетку переместить букву C или цифру 2.
M 0 0 A
8 C # 2
Первая строка содержит количество тестов (не больше 100). Далее в каждом тесте содержится четыре строки: две первые строки содержат стартовую комбинацию символов, следующие две – образец. Каждая строка содержит 4 символа (латинский алфавит и арабские цифры), пустая клетка обозначается символом #. Тесты разделены между собой пустой строкой.
Для каждого теста в выходной файл выводится строка, содержащая минимальное количество перемещений, необходимых для получения искомой комбинации. Если нужную комбинацию получить нельзя, выведите число `-1`.

Пример ввода

2
ACM8
002#
ACM#
2008

rogp
mar#
prog
ram#

Пример вывода

17
26
Четвертьфинальные соревнования Чемпионата мира Восточно-сибирского региона, 2008
loading