Codeforces Round 829 (Div. 1) |
---|
Закончено |
Андрей обожает море. Именно поэтому в разгар летнего сезона он решил отправиться на пляж, взяв с собой лежак, чтобы позагорать.
Пляж представляет собой прямоугольное поле, состоящее из $$$n$$$ строк и $$$m$$$ столбцов. Некоторые клетки этого поля свободны, на некоторых расположены дорожки, камни, ларьки и другие несдвигаемые объекты, а так же на двух соседних по стороне клетках могут стоять лежаки, расположенные как горизонтально, так и вертикально.
Андрей надеется поставить где-то свой лежак, но вот незадача, свободных мест для него может уже не быть! Именно поэтому Андрей просит вас помочь найти ему свободное место для лежака. Лежак Андрея тоже должен занимать две соседние по стороне клетки.
Если двух соседних свободных клеток нет, то для того, чтобы освободить место для лежака, придется потревожить других туристов. Для этого вы можете делать следующие действия:
В любой момент времени каждый лежак занимает две соседние клетки, не содержащие ничего другого. Вы можете двигать одновременно максимум один лежак.
Помогите Андрею освободить место для еще одного лежака, доставив минимальное количество дискомфорта окружающим, или скажите, что сделать это не получится.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 300\,000$$$, $$$1 \le n \cdot m \le 300\,000$$$) — количество строк и столбцов на поле.
Вторая строка содержит два целых числа $$$p$$$ и $$$q$$$ ($$$1 \le p, q \le 10^9$$$) — количество единиц дискомфорта, которые приносят поворот и сдвиг лежака, соответственно.
Каждая из следующих $$$n$$$ строк содержит $$$m$$$ символов, описывающие клетки поля. Все строки состоят из символов «L», «R», «D», «U», «.» и «#», задающих тип клетки. Символы «L», «R», «D» и «U» обозначают половину лежака, находящегося в этой клетке — левая, правая, нижняя или верхняя половина, соответственно. Символ «.» обозначает свободную клетку, а символ «#» — клетку, занятую несдвигаемым объектом.
Выведите одно число — минимальное количество дискомфорта, которое возникнет при освобождении места для лежака. Если освободить место для лежака невозможно, выведите число $$$-1$$$.
2 55 2.LR####LR.
4
2 34 5LR.#.#
-1
4 310 10.LR###UU#DD.
-1
3 610 7.U##.##DLR##.##LR.
24
В первом примере, передвинув верхний лежак налево, а нижний лежак направо, Андрей сможет вертикально поставить лежак посередине пляжа. Таким образом, мы доставим $$$2 + 2 = 4$$$ единицы дискомфорта. Можно показать, что доставить меньшее количество дискомфорта не получится.
Название |
---|