408488: GYM103150 B Arrowing Process

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Arrowing Processtime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There is a grid of arrows with $$$n$$$ rows and $$$m$$$ columns. A move consists of swapping two adjacent arrows that point at each other. (Two cells are adjacent if they share a side.) What is the maximum number of moves that can be performed?

Input

The input consists of a single test case. The first line of each test case consists of two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 1000$$$) — the number of rows and the number of columns in the grid, respectively.

The next $$$n$$$ lines each contain a string of length $$$m$$$. Each character of this string is one of the characters $$$\texttt{<}$$$, $$$\texttt{>}$$$, $$$\texttt{v}$$$, $$$\texttt{^}$$$, representing an arrow pointing left, right, down, and up, respectively.

Output

Output a single integer — the maximum number of moves that can be performed.

ExamplesInput
3 3
^v<
v^>
><>
Output
2
Input
6 4
>>vv
>>vv
>>vv
^^<<
^^<<
^^<<
Output
0
Note
The picture above shows the first test case. We can perform two moves to achieve the second grid. It can be shown that it is impossible to perform more than $$$2$$$ moves.

In the second test case, there is no pair of adjacent cells in the grid that contain arrows pointing at each other, so the answer is $$$0$$$.

加入题单

上一题 下一题 算法标签: