Задача C. Циклы
Задачу добавил: alef
Успешно сдано решений: 21
Конечно, доверенный человек спросил зеркальных дел мастера и о том, был ли сам мастер в зазеркальном городе.
— Несложно туда войти, да непонятно, просто ли вернуться, — отвечал мастер. — Вот заказчик это знал, он ходил туда, пока зеркало в мастерской стояло. Да и много чего он знал... Когда зеркало делалось, не мастер я был — подмастерье. Однажды ушел он в зазеркальный город, сказав, что за зеркалом покупатели придут. Велел цену за него просить как за обычное такого размера. И действительно, вскорости появились люди, которые захотели его купить. Знали они что или нет — мне неведомо. Но зеркало увезли, и с тех пор я не видел ни зеркала, ни заказчика.
Призадумался царь Гордей. Боязно в зазеркальный город кого посылать, ежели не знать, как вернуться. И вспомнил, что есть у царицы Марфы волшебные нитка с иголкой. Ежели нитка потеряется, стоит пошептать слова нужные, попросить иголку найти нитку, и она к ней дорогу укажет.
Долго ли, коротко ли, а нашелся смелый человек по имени Кондрат, решившийся в зазеркальный город пойти. Уговор был таков, что привяжет Кондрат нитку к дверной ручке, а иголку в одежде спрячет. В задачу Кондрата входило составить карту хотя бы части зазеркального города.
Улицы в зазеркальном городе являются отрезками прямых, либо параллельных, либо перпендикулярных друг другу. Кондрат решил обозначать направление движения от двери как U, к двери — D, вправо — R, а влево — L. Он фиксировал количество шагов в каждом направлении и кратко записывал, какие примечательные вещи ему попались на этом пути. Так он достаточно долго бродил по улицам, стараясь не слишком далеко уходить от того места, где была дверь. Некоторые прохожие, случалось, бросали чуть более внимательный, чем обычно, взгляд на чужестранца, но интереса к нему не проявляли.
Спустя некоторое время Кондрат понял, что прошел по некоторым улицам уже не один раз. Решив чуть передохнуть, он расположился на скамейке под раскидистым деревом, и захотел посчитать, какова же площадь изученной им части города.
За единицу длины примем длину шага Кондрата и площадь будем вычислять именно в таких квадратных единицах. Когда Кондрат находится в некотором квадрате единичной площади, то он может изучить квадратную окрестность со стороной 2*K+1 единиц с центром в том квадрате, где он находится. Ваша задача — по записям Кондрата посчитать площадь, которую он изучил.
Формат входного файла input.txt
Первая строка — два целых числа N и K (1 ≤ N ≤ 1000, 0 ≤ K ≤ 1000) через пробел; число N — количество записей, сделанных Кондратом, число K — количество шагов, определяющее размер квадратной окрестности, описанной в условии.
Вторая строка является строкой из N символов U, D, R, L, записанных без пробелов, задающей путь Кондрата. Символ U означает, что Кондрат сделал шаг в направлении «вверх», D — в направлении «вниз», R — в направлении «вправо» и L — в направлении влево.
Формат выходного файла output.txt
Первая строка — целое число — площадь изученной Кондратом части города
Пример входного файла
55 1
UUUUUURRRRRRRRDDDDDDDDDDLLLLLLLLLLLLLLUUUUUURRRRRRRRRRR
Пример выходного файла
165