eolymp
bolt
Try our new interface for solving problems
Məsələlər

Пятнашки

Пятнашки

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Пятнашки - это популярная головоломка, придумання в 1878 году Ноем Чепмэном. Представляет собой набор одинаковых квадратных костяшек с нанесёнными числами, заключённых в квадратную коробку. Длина коробки в четыре раза больше длины стороны костяшек, соответственно в коробке остаётся незаполненным одно квадратное поле. Цель игры - перемещая костяшки по коробке, добиться упорядочивания их по номерам так, как показано на следующе картинке.

Допустимые ходы можно описать в терминах перемещения пустой клетки: её переместить вправо ("R"), влево("L"), вверх ("U") или вниз ("D"), меннясь местами с соседней костяшкой в соответствующем направлении.

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

Giriş verilənləri

Входной файл состоит из 4 строк. В каждой записано по 4 числа от 0 до 15, которые задают номера костяшек, находящихся в соответствующих клетках в начальном состоянии головоломки (0 соответствует пустой клетке). Каждое из чисел встречается по одному разу.

Çıxış verilənləri

В выходной файл необходимо вывести одну строку. Если для заданного состояния не существует решения, выведите "NO SOLUTION". Если же решение есть, то эта строка должна определять кратчайшую последовательность ходов, которая приводит головоломку к требуемому финальному состоянию. Если длина оптимальной последовательности превышает 45 ходов, выведите вместо неё строку "TOO LONG".

Nümunə

Giriş verilənləri #1
2 3 4 0
1 5 7 8
9 6 10 12
13 14 11 15
Çıxış verilənləri #1
LLLDRDRDR
Mənbə III International Summer School Programming in Sevastopol 2012