問題文
H 行 W 列组成的网格。从上面 i 行,从左起 j 标记列中的方块
表示为 (i,j) 。在每个方格内
如果写入任何字符 E, F, G , (i,j) 中写入的字符是给定的字符串 S_i 的
已知 j 与第一个字符相同。
始,质量 一块被放置在 (1,1) 上。你的目标是重复将这块棋子向四个方向移动到相邻方格的操作。 目的是在 (H,W) 上放置一个棋子。
但是,每次操作都无法将您移动到与您当前所在的方块具有相同字母的方块。 判断是否可以在
质量 在 (H,W) 上放置棋子,如果可以,求最少的操作次数。
制約
- 2\le H\le 1000
- 2\le W\le 1000
- H,W 是一个整数 如果不可能将棋子放置在
- S_i 为
E,F,G组成长度为 W 的字符串
入力
输入将以以下格式从标准输入给出。
H W S_1 S_2 \vdots S_H
出力
质量
在 (H,W) 上
输出 -1 。
如果可能的话质量
输出将棋子放置在 (H,W) 上所需的最少操作次数。
入力例 1
3 4 EEGE GFFF GFEE
出力例 1
7
质量 在 (1,1) 正方形按顺序从 (2,1),(2,2),(1,2),(1,3),(1,4),(2,4),(3,4) 您可以按顺序移动它。
本例中的操作次数为 7 次, 7 不可能将棋子放置在 (3,4) 上。因此, 请输出 7 。
入力例 2
2 2 EE FF
出力例 2
-1
质量
在 (2,2) 上。因此,
请输出 -1 。
入力例 3
5 6 FEGFGF FEEFEE FFGGFE GEGGEE GGEGFE
出力例 3
9