Пятнашки

Пятнашки – популярная головоломка, представляющая собой набор одинаковых квадратных костяшек с нанесёнными числами, заключённых в квадратную коробку, имеющей размер 4х4. Цель игры — перемещая костяшки по коробке добиться упорядочивания их по номерам (как показано на рисунке), желательно сделав как можно меньше перемещений. Известно, что не любое размещение костяшек на доске позволяет получить решаемую задачу.

Рассмотрим более общую игру для доски N x N, где будет использоваться N²-1 костяшек с числами. Самый надежный способ получить решаемую головоломку – это провести последовательность произвольных ходов из конечного решенного состояния. Такой набор действий удобно представить в виде последовательности символов, обозначающих направления движения пустого места на доске. Пусть «U», «D», «L» и «R» – возможные направления движения, обозначающие «вверх», «вниз», «влево» и «вправо» соответственно. Игровую коробку удобно представить матрицей, а костяшки – числами. Пустое место будем обозначать цифрой «0».

Например, для N=3 первоначально мы будем иметь следующую доску:

 1 2 3
 4 5 6
 7 8 0

После команды «ULD» мы получим следующее состояние:

 1 2 3
 4 8 5
 7 0 6

Заметим, что команда «URLD» невыполнима в связи с невозможностью на втором ходе передвинуть пустое поле вправо.

По заданному размеру поля и последовательности команд требуется определить конечное состояние игрового поля.

Входные данные

Первая строка входного файла INPUT.TXT содержит натуральное число N – размерность игрового поля (N ≤ 20). Во второй строке располагается последовательность команд (не более 10⁴ действий), содержащая только символы «U», «D», «L» и «R», записанные слитно.

Выходные данные

В выходной файл OUTPUT.TXT выведите таблицу конечного состояния игрового поля. В том случае, когда команда не выполнима, в выходной файл следует вывести только текст «ERROR K», где K – номер хода, на котором произошла ошибка. При выводе допускается использование избыточных пробелов и переносов строк.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки] [Решение]