文件读写

• 输入文件 rover.in
• 输出文件 rover.out

限制

• 1000ms
• 512MB

题目描述

程老师的仓库是一个 $n$ 行 $m$ 列的网格，格子 $(i,j)$ 表示第 $i$ 行第 $j$ 列的格子。每个格子的地面上都印着一个导向箭头，箭头只有四种，分别是 >（向右）、<（向左）、^（向上）、v（向下），指向与之相邻的某一个格子。程老师遥控一辆搬运车在仓库里运货，出发点是左上角的格子 $(1,1)$，终点是右下角的格子 $(n,m)$。车每走一步，所在的格子就从当前格变成一个与之相邻的格子；同一个格子允许反复经过。

车每走一步只有两种驾驶方式。自动导航：车沿当前格子所印箭头的方向移动到相邻格子；若当前格子的箭头指向仓库之外，车无法沿箭头开出，此时自动导航不可执行，但这不影响手动驾驶。手动驾驶：车向上、下、左、右四个相邻格子中的任意一个移动一步，但不能移出仓库。手动驾驶费神：一次手动驾驶之后，接下来的 2 步必须使用自动导航，第 3 步起才重新获得手动驾驶的资格。自动导航不消耗任何代价，只要当前格子的箭头顶用，随时可以执行。出发时（第 1 步之前）车处于可手动状态。

车到达终点所在的格子即视为运货完成，不区分是以哪种驾驶方式到达的。程老师想知道，从 $(1,1)$ 出发把货送到 $(n,m)$，最少需要走多少步；若无论怎样驾驶都无法送达，则输出 $-1$。

输入格式

从文件 rover.in 中读入数据。

第一行两个整数 $n, m$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，仅含 >、<、^、v 四种字符。其中第 $i$ 行的第 $j$ 个字符表示格子 $(i,j)$ 上印的箭头。

输出格式

输出到文件 rover.out 中。

输出一行一个整数，表示从 $(1,1)$ 到 $(n,m)$ 的最少步数；无法送达时输出 $-1$。

数据范围

对于所有测试数据，保证 $1 \leq n, m \leq 1000$，且 $n \times m \geq 2$。

特殊性质 A：所有箭头只含 > 和 v 两种。

特殊性质 B：所有位于网格边界的箭头都不指向网格外。

3 3
>v>
^><
^<<

4

2 3
>>v
^<<

3

样例解释

样例 1：4 步可以送达。第 1 步在 $(1,1)$ 使用手动驾驶向右移动到 $(1,2)$，这一步使接下来的 2 步只能使用自动导航；第 2 步沿 $(1,2)$ 的箭头 v 自动导航到 $(2,2)$；第 3 步沿 $(2,2)$ 的箭头 > 自动导航到 $(2,3)$，此时强制自动的 2 步已经走完，第 4 步重新获得手动资格，从 $(2,3)$ 向下移动到 $(3,3)$ 完成。

少于 4 步则不行。没有任何一个格子的箭头指向 $(3,3)$，最后一步只能是手动驾驶，这就要求第 2 步走完时车已经停在 $(2,3)$ 或 $(3,2)$。这两格与 $(1,1)$ 的行、列之差加起来都是 3，而每走一步最多让这个差减少 1，所以 2 步之内到不了其中任何一格。

样例 2：全程使用自动导航即可送达，$(1,1) \to (1,2) \to (1,3) \to (2,3)$ 共 3 步，中途不需要手动驾驶。起点与终点横向相差 2 格、纵向相差 1 格，每走一步至多只能补上其中的 1 格，3 步已经是最少的。