Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Пятнашки

(Время: 1 сек. Память: 16 Мб Сложность: 35%)
Пятнашки

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

Рассмотрим более общую игру для доски N x N, где будет использоваться N2-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). Во второй строке располагается последовательность команд (не более 104 действий), содержащая только символы «U», «D», «L» и «R», записанные слитно.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
13
ULDLURULD
8 1 3
0 2 5
4 7 6
22
URL
ERROR 2

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru