|
Фатализм
(Время: 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.TXT | OUTPUT.TXT |
1 | 5 1 2
X...X
3 1 L
4 1 R | 2 |
2 | 4 4 4
X..X
....
....
X..X
1 3 R
3 4 U
4 2 L
2 1 D | 1 |
3 | 4 5 3
....
....
....
....
....
1 4 R
3 5 U
4 5 U | 4 |
4 | 3 6 5
.X.
.X.
.X.
...
...
.X.
1 4 R
2 5 U
3 5 U
1 6 R
3 6 L | 5 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |