Даю 70 баллов информатика 6 класс



Задача 2: Влад и дрон

Недавно Влад победил на олимпиаде и выиграл современный квадрокоптер — дрон. Влад

прикрутил к квадрокоптеру камеру, поднял его в воздух и начал фотографировать

интересующие его места.

Влад раздобыл карту местности, разбил её на квадраты и закрасил на ней интересующий

его участок. Получилась схема, изображённая на рисунке 2. Ему необходимо сделать

фотографии всех закрашенных квадратов. Теперь он хочет написать программу для дрона,

поставить дрона в какой-нибудь закрашенной клетке и запустить его.

Программа для дрона — последовательность букв U, D, L, R, которые, соответственно,

двигают дрон вверх, вниз, влево или вправо на 1 клетку. В процессе выполнения

программы дрон сфотографирует каждую клетку ровно столько раз, сколько побывает на

ней. Клетка, в которую дрон помещается вначале, сразу фотографируется им. Владу

важно, чтобы были сфотографированы только закрашенные клетки. Одну и ту же клетку

можно фотографировать несколько раз.

К сожалению, денег у Влада не очень много, поэтому он смог позволить себе очень

маленькую карту памяти. Влада интересует, какую программу для дрона надо написать,

чтобы сфотографировать только закрашенные клетки, сделав при этом как можно меньше

фотографий.

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

программу «DLRDRLD», поместив изначально дрон в клетку (1, B), находящуюся на

пересечении 1-й строки и B-го столбца. В этом случае будет сделано 8 фотографий —

минимально возможное количество.