AT_guildfes_2026_final_f EGFパス

$ H $ 行 $ W $ 列のグリッドが与えられます。上から $ i $ 行目、左から $ j $ 列目のマスをマス $ (i,j) $ と表します。各マスには `E`, `F`, `G` のいずれかの文字が書かれており、マス $ (i,j) $ に書かれた文字は与えられる文字列 $ S_i $ の $ j $ 文字目と同じです。 はじめ、マス $ (1,1) $ にコマが置かれています。あなたの目標はこのコマを四方向に隣接するマスに動かす操作を繰り返してマス $ (H,W) $ にコマが置かれた状態にすることです。 ただし、各操作で今いるマスと同じ文字が書かれたマスへ移動することはできません。 マス $ (H,W) $ にコマが置かれた状態にすることが可能か判定し、可能な場合は操作回数の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_H $

マス $ (H,W) $ にコマが置かれた状態にすることが不可能な場合は `-1` を出力せよ。 可能な場合はマス $ (H,W) $ にコマが置かれた状態にするために必要な操作回数の最小値を出力せよ。

### Sample Explanation 1 マス $ (1,1) $ から順にマス $ (2,1),(2,2),(1,2),(1,3),(1,4),(2,4),(3,4) $ と順に動かしていけば良いです。 この場合の操作回数は $ 7 $ 回で、 $ 7 $ 回未満でマス $ (3,4) $ にコマが置かれた状態にすることはできません。したがって、 $ 7 $ を出力してください。 ### Sample Explanation 2 マス $ (2,2) $ にコマが置かれた状態にすることはできません。したがって、 `-1` を出力してください。 ### Constraints - $ 2\le H\le 1000 $ - $ 2\le W\le 1000 $ - $ H,W $ は整数 - $ S_i $ は `E`, `F`, `G` からなる長さ $ W $ の文字列