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

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

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++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2005 / 2006
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014 7-8 классы
 2013 / 2014 9-11 классы
 2014 / 2015 7-8 классы
 2014 / 2015 9-11 классы
 2015 / 2016 7-8 классы
 2015 / 2016 9-11 классы
 2016 / 2017 7-8 классы
 2016 / 2017 9-11 классы
 2017 / 2018 7-8 классы
 2017 / 2018 9-11 классы
 2018 / 2019 7-8 классы
 2018 / 2019 9-11 классы
 2019 / 2020 7-8 классы
 2019 / 2020 9-11 классы
 2020 / 2021 7-8 классы
 2020 / 2021 9-11 классы
 2021 / 2022 7-8 классы
 2021 / 2022 9-11 классы
 A. Колокол
 B. Пятнашки
 C. Манхэттенские улицы
 D. ДНК
 E. Мусорщик

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