Сможете ли вы остаться в пределах сетки?
При создании компьютерной игры вы работаете с сеткой размером
h на w. В каждой ячейке указано направление (<>v^), показывающее, куда нужно переместиться, если вы окажетесь в этой ячейке.Вы начинаете в случайной ячейке и двигаетесь в направлении, которое указано на этой ячейке. Иногда это приводит к тому, что вы выходите за границы сетки, и тогда игра заканчивается.
> | > | v | > | > |
^ | < | < | v | < |
v | ^ | ^ | < | > |
< | v | ^ | > | < |
Поскольку вы являетесь разработчиком игры, вы хотите убедиться, что таких «опасных» ячеек не слишком много. Поэтому вы решаете вычислить количество ячеек, начиная из которых вы никогда не покинете пределы сетки.
Input
В первой строке входных данных содержатся два целых числа
h и w (1 ≤ h, w ≤ 1000).В следующих
h строках расположены w символов, указывающих направление, в котором нужно двигаться из соответствующей ячейки (<>v^).Output
Программа должна вывести количество ячеек, начиная из которых вы всегда будете оставаться на сетке.
Examples
Input | Output |
4 5
>>v>>
^<<v<
v^^<>
<v^>< | 14 |
Explanation
> | > | v | > | > |
^ | < | < | v | < |
v | ^ | ^ | < | > |
< | v | ^ | > | < |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB