← 返回题目列表

AtCoder · guildfes_2026_final_f

F. EGF 通行证

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

問題文

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