Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Фатализм

(Время: 1 сек. Память: 16 Мб Сложность: 42%)

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

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

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

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

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
15 1 2
X...X
3 1 L
4 1 R
2
24 4 4
X..X
....
....
X..X
1 3 R
3 4 U
4 2 L
2 1 D
1
34 5 3
....
....
....
....
....
1 4 R
3 5 U
4 5 U
4
43 6 5
.X.
.X.
.X.
...
...
.X.
1 4 R
2 5 U
3 5 U
1 6 R
3 6 L
5

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

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ