← 返回题目列表

Codeforces · 382/D

D. 克塞尼亚和典当

中文机器翻译题面 查看原题

Ksenia 有一个大小为 n × m 的棋盘。棋盘的每个单元格包含字符之一:“<”、“">”、“^”、“v”、“#”。包含字符“#”的单元格被阻止。我们知道所有接触边界的棋盘单元都被阻挡。

Ksenia 正在棋盘上玩两个棋子。最初,她将棋子放在棋盘上。当且仅当该单元格被阻挡时,棋盘的一个单元格可以包含两个棋子。在其他情况下,两个棋子不能站在一个牢房中。当克塞尼亚将棋子放在棋盘上时,游戏开始。在一次移动中,Ksenia 将每个 pawn 沿着相应 pawn 所在单元格上绘制的箭头方向移动到相邻单元格的一侧(如果 pawn 位于“#”上,则它不会移动)。假设 Ksenia 同时移动棋子(参见第二个测试用例)。

当然,Ksenia 是为了积分而战。如何计算每场比赛的得分?很简单!让我们数一下第一个棋子做了多少次动作,第二个棋子做了多少次动作,将这两个数字相加——这就是游戏的得分。

Ksenia 想知道:她能获得的最大分数是多少(为此,她应该在游戏早期将棋​​子放置在最佳位置)。帮助她找到那个号码。

输入

第一行包含两个整数,n 和 m (1 ≤ n, m ≤ 2000) — 棋盘的大小。接下来的 n 行每行包含 m 个字符——棋盘的描述。每个字符都是以下字符之一:“<”、“">”、“^”、“v”、“#”。

保证表格的边界单元格是阻塞单元格(带有字符“#”)。

输出

如果 Ksenia 可以获得无限多个点,则打印 -1。否则,打印她可以获得的最大分数。

示例

输入 #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