Фатализм

Роботу Прайму (конструктору роботов) надоели его творения – они получаются слишком тупыми и бездумными, и среди них не найти собеседника и даже просто мыслителя, достойного общаться с самим Праймом, великим и неповторимым. Прайм испробовал уже все известные ему методы, но создать себе подобного до сих пор не получилось. В отчаянии он придумал себе игру, чтобы как то отвлечься от своей неразрешимой проблемы, преодолеть творческий кризис и заодно пустить побольше своих творений по правильному пути. Игра называется «Фатализм» и заключается в следующем.

Прайм создает лабиринт размера m×n клеток, огороженный со всех сторон стенами. Каждая клетка лабиринта – либо свободное пространство, либо стена. В начальный момент времени в некоторых клетках, где нет стены, стоят роботы и смотрят в одном из четырех направлений. Никакие два робота не стоят в одной клетке.

Каждый робот движется с постоянной скоростью – одна клетка в секунду – в направлении, в котором он смотрит, и светит лазером в этом же направлении до ближайшей стены. В конце каждой секунды некоторые роботы взрываются. Это происходит в трех случаях:

• если робот оказался за пределами лабиринта или в клетке, которая заполнена стеной, то он взрывается;
• если в какой-то клетке оказалось два или более робота, то все они взрываются;
• для оставшихся роботов, если какой-то из них оказался между другим роботом и стеной, до которой светит луч его лазера, то этот робот взрывается. Взрывы от лучей лазера происходят одновременно: тем не менее, даже если какой-то робот взорвался, луч его лазера успевает взорвать всех роботов, которые находились между ним и стеной, до которой светит его лазер.

Известно, что в начальный момент времени никакой робот не светит на другого робота лазером. Взорвавшиеся роботы не оказывают влияния на ситуацию в лабиринте в последующие секунды. Понятно, что жизнь любого робота будет в таких условиях очень недолгой. Прайм хочет выяснить, сколько времени просуществует самый долгоживущий из них. Выясните, сколько времени пройдет до того момента, как все роботы взорвутся.

Входные данные

В первой строке входного файла INPUT.TXT заданы через пробел три числа m, n и k (1 ≤ m, n, k ≤ 100). В следующих n строках содержится ровно по m символов в каждой: i-ый символ в j-ой из этих строк равен «X» (икс большое), если соответствующая клетка (i, j) занята стеной, и «.» (точка), если эта клетка пуста. Далее идут k строк, описывающие роботов. Каждая из них имеет вид (x_i,y_i,z_i), где x_i и y_i – координаты робота (1 ≤ x_i ≤ m, 1 ≤ y_i ≤ n), а z_i – один из четырех символов направления: символ «U» (up) соответствует уменьшению координаты y, символ «L» (left) – уменьшению координаты x, символ «D» (down) – увеличению y, а символ «R» (right) – увеличению x. Все числа во входном файле целые.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число – сколько секунд пройдет до того момента, как все роботы взорвутся.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]