Ksenia and Pawns

题意翻译

有一个 $n\times m$ 的棋盘，棋盘中的每一格都写着以下五个字符之一：`<`, `>`, `^`, `v`, `#`，其中 `#` 表示格子被阻挡。已知所有位于棋盘边界的格子都被阻挡。 初始时把两个士兵任意放在棋盘上。除了被阻挡的格子可容纳两个士兵以外，其余格子最多能容纳一个士兵。在游戏的每一轮中，每个士兵向所在格子的箭头方向移动一格（若在被阻挡的格子上则无法移动）。假设两个士兵是同时移动的。 游戏的得分记为两个士兵所走过的步数之和。对于不同的士兵初始位置，得分也不相同。请输出可能获得的最大得分。若得分可达到任意大，输出 $-1$。

题目描述

Ksenia has a chessboard of size $ n×m $ . Each cell of the chessboard contains one of the characters: "<", ">", "^", "v", "\#". The cells that contain character "\#" are blocked. We know that all chessboard cells that touch the border are blocked. Ksenia is playing with two pawns on this chessboard. Initially, she puts the pawns on the chessboard. One cell of the chessboard can contain two pawns if and only if the cell is blocked. In other cases two pawns can not stand in one cell. The game begins when Ksenia put pawns on the board. In one move, Ksenia moves each pawn to a side adjacent cell in the direction of arrows painted on the cell on which the corresponding pawn sits (if the pawn sits on "\#", it does not move). Assume that Ksenia moves pawns simultaneously (see the second test case). Of course, Ksenia plays for points. How can one calculate the points per game? Very simply! Let's count how many movements the first pawn made and how many movements the second pawn made, sum these two numbers — it will be the resulting score of the game. Ksenia wonders: what is the maximum number of points she can earn (for that, she should place the pawns optimally well early in the game). Help her and find that number.

输入输出格式

输入格式

The first line contains two integers, $ n $ and $ m $ $ (1<=n,m<=2000) $ — the sizes of the board. Each of the following $ n $ lines contains $ m $ characters – the board's description. Each character is one of the characters: "<", ">", "^", "v", "\#". It is guaranteed that the border cells of the table are blocked cells (with character "\#").

输出格式

If Ksenia can get infinitely many points, print -1. Otherwise, print the maximum number of points she can get.

输入输出样例

输入样例 #1

1 1
#

输出样例 #1

0

输入样例 #2

3 4
####
#>^{}#
####

输出样例 #2

3

输入样例 #3

3 4
####
#><#
####

输出样例 #3

-1

输入样例 #4

7 5
#####
##v##
##v##
#####
##^{}##
##^{}##
#####

输出样例 #4

4

输入样例 #5

7 5
#####
##v##
##v##
##<##
##^{}##
##^{}##
#####

输出样例 #5

5