Пятнашки
Пятнашки
Пятнашки - это популярная головоломка, придумання в 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ə
2 3 4 0 1 5 7 8 9 6 10 12 13 14 11 15
LLLDRDRDR