images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
24/04/2024 20:42:15

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

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

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

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

39590.png
Для проверки интеллекта роботов используется головоломка, показанная на рисунке, в которой цифры от 1 до 7 располагаются в ячейках, а одна из ячеек свободна. Необходимо переставить цифры, используя свободную ячейку, чтобы цифры расположились так, как показано на рисунке. Перемещение буквы в свободную ячейку возможно, только если ячейки соединены линией.
Напишите программу, которая определяет минимальное количество ходов для решения головоломки.
Первая строка ввода содержит одно целое число – количество тестов `N` (`1\ ≤\ N\ ≤\ 40000`). Далее следует `N` строк, содержащих перестановку чисел 0, 1, 2, 3, 4, 5, 6, 7 – начальную позицию. Числа перечисляются в порядке чтения слева направо, сверху вниз. Число 0 обозначает пустую ячейку.
Для каждой начальной позиции вывести на отдельной строке сначала минимальное количество ходов, затем саму последовательность ходов – последовательность цифр от 1 до 7, которые нужно перемещать на очередном ходе в свободную ячейку. Если существует несколько минимальных вариантов для последовательности ходов, то можно вывести любой из них. Гарантируется, что все начальные позиции для головоломки имеют решение.

Пример ввода

3
1 2 3 4 0 5 6 7
2 1 3 4 0 5 6 7
0 1 2 3 4 5 6 7

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

0
7 5321235
18 213451323154213124
loading