题目描述

小飞侠被困在了一个 $N \times M$ 的魔法迷宫中。迷宫由各种方格组成，包括空地（.）、墙壁（#）、起点（S）和终点（E）。

小飞侠拥有一种名为“暗影跳跃”的特殊技能。他的移动方式如下：

1. 普通行走： 向上下左右四个方向移动一格。每次移动消耗 1 单位时间。
2. 暗影跳跃： 向上下左右四个方向直接跳跃两格（例如，从 $(x, y)$ 跳到 $(x+2, y)$）。
   • 跳跃可以“跨越”中间的障碍物（即中间那格可以是墙壁）。
   • 但是，跳跃的落脚点必须是空地或终点，不能是墙壁。
   • 每次跳跃消耗 1 单位时间。

为了平衡体力，小飞侠不能连续两次使用“暗影跳跃”。也就是说，如果你刚刚使用了一次跳跃，那么下一步必须进行“普通行走”；如果你刚刚进行了“普通行走”（或者刚开始在起点），那么下一步既可以行走也可以跳跃。

请计算小飞侠从起点到达终点所需的最少时间。如果无法到达，输出 -1。

输入格式

第一行包含两个整数 $N, M$ ($1 \le N, M \le 1000$)，表示迷宫的行数和列数。 接下来 $N$ 行，每行包含 $M$ 个字符，表示迷宫的布局。

• . 表示空地
• # 表示墙壁
• S 表示起点
• E 表示终点

输出格式

输出一个整数，表示到达终点的最少时间。若无法到达，输出 -1。

输入样例 1:

4 5
S.#..
..#..
#.#..
...E.

输出样例 1:

4

样例解释 1

路径如下：

1. (1,1) -> (1,2) [行走, 耗时1, 状态变为可跳]
2. (1,2) -> (1,4) [跳跃, 跨过墙壁(1,3), 耗时1, 状态变为不可跳]
3. (1,4) -> (2,4) [行走, 耗时1, 状态变为可跳]
4. (2,4) -> (4,4) [跳跃, 跨过障碍(3,4), 耗时1, 到达终点] 总耗时 4。

输入样例 2:

3 3
S#.
###
#.E

输出样例 2:

-1