Протоптанный кабель
Натан О. Дэвис управляет компанией, которая владеет популярным веб-сервисом с множеством пользователей. В его офисе полно серверов, маршрутизаторов и запутанных сетевых кабелей.
Сейчас его беспокоят эти кабели, так как они создают множество проблем. Например, сотрудники часто спотыкаются о кабели. Если кабель отключен, это не приводит к повреждениям, но если он подключен, компьютеры могут упасть и сломаться. Натан планирует установить новый компьютер и проложить новый кабель, стремясь минимизировать количество раз, когда сотрудники будут перешагивать через него.
Офис представлен в виде двумерной сетки размером H×W ячеек. Новый кабель должен пролегать вдоль границ ячеек, а его концы находятся в углах ячеек. Сетка имеет координаты с нулевым началом, где верхний левый угол — это (0, 0).
Каждый сотрудник начинает работу в определенной ячейке и перемещается по офису в соответствии с фиксированным повторяющимся шаблоном. Шаблон описывается строкой из символов U, D, L и R, где U — движение вверх, D — вниз, R — вправо, а L — влево. Например, UULLDDRR означает последовательное движение вверх, вверх, влево, влево, вниз, вниз, вправо и вправо. Сотрудник повторяет этот шаблон T раз. Если сотрудник выходит за пределы сетки, он остается в текущей ячейке.
Ваша задача — на основе шаблонов перемещений сотрудников и позиций концов нового кабеля определить оптимальное размещение кабеля, чтобы минимизировать общее количество пересечений кабеля сотрудниками.
Входные данные
Первая строка ввода содержит три целых числа: размеры офиса W, H (1 ≤ W, H ≤ 500) и количество сотрудников N (1 ≤ N ≤ 1000). Следующая строка содержит две пары x−y (0 ≤ x ≤ W, 0 ≤ y ≤ H), которые указывают позиции концов кабеля. Эти координаты представляют ячейки, к которым кабель подключен в их верхнем левом углу. Значения x=W и y=H означают правый и нижний края самой правой и нижней ячеек соответственно.
Далее следуют описания начальных позиций сотрудников и их шаблонов перемещений. Каждое описание начинается с пары x-y (0 ≤ x < W, 0 ≤ y < H), обозначающей начальную ячейку сотрудника. Затем идет целое число T (1 ≤ T ≤ 100) и строка, состоящая из символов U, D, L, R. Длина строки шаблона от 1 до 1000. Эти две строки повторяются N раз.
Выходные данные
Выведите минимальное количество раз, когда сотрудники пересекут кабель, в одной строке.