<ПРЕД Задача:
СЛЕД>
Задачу решили 65 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Головоломка "Пятнашки"

Time limit = 5 секунд(ы)

Memory limit = 33000 Kb

Головоломка "пятнашки" заключается в следующем. Даны квадратные фишки с номерами 1, 2, 3, ..., 15, которые уложены в плоскую коробочку размера 4x4. Коробочка разделена на 16 ячеек, и каждая фишка лежит точно в одной ячейке. Одна из ячеек пустая. Разрешено за один ход одну из фишек, соседних с пустой ячейкой, передвинуть в эту ячейку.

1234
5678
9101112
131415 

Целевое состояние головоломки.

a1a2a3a4
a5a6a7a8
a9a10a11a12
a13a14a15a16;

Начальное состояние головоломки.

На вход даётся начальное расположение головоломки пятнашки. Необходимо определить, можно ли её решить, и если можно, то вывести последовательность ходов, которые её решают.

Вход. Строка с числами a1, a2, ..., a16, которые описывают начальное состояние головоломки.

Выход. Выведите NO, если головоломку нельзя решить. Если головоломку можно решить, то выведите YES, а в следующей строке выведите последовательность ходов, которые нужно сделать, чтобы достичь целевого состояния. Ход обозначается одним из четырех символов: "r", "l", "u", "d" (right, left, up, down), — и соответствует направлению перемещения пустой ячейки (вправо, влево, вверх и вниз, соответственно). Число ходов должно быть меньше 1000. Пробелы между буквами ставить не нужно.

Вход#1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0
Выход#1
YES

Вход#2
1 2 3 4 5 6 7 8 9 10 0 11 13 14 15 12
Выход#2
YES
rd

Автор:
фольклор, тесты и описание Антышев Евгений Павлович.
3 мая 2006

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 52.3.228.47