Входной файл: gridlock.in Выходной файл: gridlock.out Время на тест: 2 секунды Автор задачи: А.Н. Данченко Тесты к задаче:Скачать
Gridlock - это реализация настольной игры "Rush Hour", созданной компанией
Binary Arts. Игровое поле представляет собой квадрат 6 на 6 клеток с одним
выходом. На этом поле задана система координат, так что левая верхняя клетка
имеет координаты (1, 1), ос ь X направлена вниз, а ось Y - вправо. Выход
находится всегда справа на третьей горизонтали. В поле находятся N вертикальных
или горизонтальных блоков длины 2 или 3 и единичной ширины. На одной горизонтали
или вертикали не бывает двух блоков длины 3 или трех блоков длины 2. На третьей
горизонтали находится горизонтальный блок длины 2, который надо вытащить через
выход. Больше горизонтальных блоков на этом уровне нет. На рисунке показан
пример начальной расстановки блоков.
Игроку разрешается двигать горизонтальные блоки по горизонтали и вертикальные по
вертикали. За один шаг блок можно передвигать на любое число клеток до тех пор,
пока он не упрется в край поля или в другой блок. Вам требуется написать
программу, которая р ассчитывает минимальное число передвижений блоков,
необходимых для завершения игры.
Входные данные находятся в текстовом файле
GRIDLOCK.IN и состоят из нескольких строк. Первая строка содержит десятичную
запись числа N. Каждая из последующих N строк содержит описание блоков в
формате: T X Y L , где символ T равен 'V' или 'H', в зависимо сти от того,
вертикальный это блок или горизонтальный; X Y - числовые значения координат
клетки, в которой находится левый верхний квадрат блока; L - длина блока. Первым
всегда описывается блок, который надо вытащить. Гарантируется, что для всех
предложе нных тестов первый блок можно будет вытащить.
Выходные данные помещаются в текстовый файл GRIDLOCK.OUT. Первая строка этого
файла содержит Moves - минимальное число перемещений, необходимых для
выталкивания первого блока через выход. Каждая из последующих Moves-1 строк
содержат описание одного пере мещения (кроме последнего) и содержит номер блока
(т.е. номер появления его описания во входном файле) и число клеток, на которое
этот блок перемещается по направлению соответствующей оси. Если задача решается
неоднозначно, Вы можете указать любое из воз можных решений.
Пример входных данных 6
H 3 1 2
V 1 2 2
V 1 4 3
V 1 6 3
H 4 5 2
H 6 1 2