Графический редактор <<Хамелеон>>
Юный информатик осваивает новый графический редактор «Хамелеон». Этот редактор обладает необыкновенной простотой. Он поддерживает ровно два цвета — чёрный и белый, и один инструмент — «Хамелеон».
Поле редактора — это квадрат N × N клеток. На одной из клеток поля находится курсор-хамелеон. Его можно передвигать в пределах поля в четырех направлениях — вверх, вниз, вправо или влево ровно на одну клетку. Цвет курсора всегда должен совпадать с цветом клетки, в которой он находится. Для этого, когда он перемещается на клетку другого цвета, должно произойти одно из двух событий: либо курсор меняет свой цвет на цвет этой клетки, либо наоборот — клетка меняет свой цвет на цвет курсора. Например, если курсор перемещается из чёрной клетки в белую, либо он должен перекраситься в белый цвет, либо белая клетка, в которой он теперь находится, должна стать чёрной. Если клетка и курсор имеют одинаковый цвет, то их цвет не изменяется.
Изначально курсор имеет чёрный цвет и находится в левой верхней клетке поля. Эта клетка также окрашена в чёрный цвет. Все остальные клетки поля окрашены в белый цвет.
Требуется написать программу, определяющую последовательность действий курсора-хамелеона, после выполнения которой на поле получится картинка, заданная во входных данных.
В первой строке входного файла задано число N (5 ≤ N ≤ 100) — размер поля.
В следующих N строках описывается картинка, которую необходимо получить. Каждая строка описания картинки имеет длину N и состоит из символов «W», если соответствующая клетка белая, и «B», если чёрная.
Последняя строка файла содержит номер теста.
Выходной файл должен содержать одну строку с описанием искомой последовательности действий.
Для обозначения перемещения влево, вверх, вправо или вниз с изменением цвета курсора следует использовать буквы «l», «u», «r» или «d» соответственно. Для обозначения перемещения влево, вверх, вправо или вниз с изменением цвета клетки следует использовать буквы «L», «U», «R» или «D» соответственно. Если курсор перемещается на клетку своего цвета, можно использовать как заглавную, так и строчную букву.
В этой задаче тестовые данные доступны участникам. Скачать тестовые данные.
Тесты нумеруются в соответствии с названиями файлов от 0 до 20. Тест из примера имеет номер 0, он используется для предварительной проверки. Тесты с номерами с 1 по 20 включительно используются для окончательной проверки.
Окончательная проверка данной задачи осуществляется на наборе из 20 тестов. Каждый тест оценивается из 5 баллов. Тесты оцениваются независимо.
Тест считается пройденным, если выведенная последовательность содержит не более 5 000 000 действий и приводит к правильному результату.
Первые 10 тестов оцениваются в 5 баллов, если тест пройден.
Оставшиеся 10 тестов оцениваются следующим образом. Если тест пройден, то:
- в 5 баллов, если ответ содержит не более 3N2 действий;
- в 4 балла, если ответ содержит не более 5N2 действий;
- в 3 балла, если ответ содержит не более 10N2 действий;
- в 2 балла, если ответ содержит не более 2.5N3 действий;
- в 1 балл, если ответ содержит не более 5 000 000 действий.
Для просмотра последовательности действий участнику предоставляется визуализатор. Скачать архив визуализатора.
При запуске визуализатора без параметров будет предложено выбрать входной и выходной файлы для визуализации. Имя входного и выходного файла также можно указать в виде параметров командной строки, запустив команду «visualize.cmd <входной файл> <выходной файл>».
5 BWWWW BWWWW BWBWW WWWWW WWWWW 0
DDRRdlU