ZDD Maze

2 secs 1024 MB

問題文

各マスに D か Z が書かれた、 $H \times W$ の迷路があります。
あなたは、左上のマスからスタートし、上下左右の移動を繰り返し（同じマスを何回通ってもよい）、右下のゴールに行きたいです。
ただし、この迷路から脱出するには、左上のスタートから右下のゴールまでに通ったマスに書かれた文字が、
Z(スタートマス)→D→D→Z→D→D→......→Z→D→D(ゴールマス)
となっていなければなりません。ここで、途中でゴールマスを何回でも通ってもよいことに注意してください。
あなたは脱出できるでしょうか？また、最小で何回の移動で脱出できますか？

制約

$2 \le H, W \le 1000$
$H, W$ は整数
$S_{i, j}$ は D か Z
$S_{1, 1} =$ Z、 $S_{H, W} =$ D

入力

入力は以下の形式で標準入力から与えられます。

$H\ W$
$S_{1,1}S_{1,2}\dots S_{1,W}$
$\dots$
$S_{H,1}S_{H,2}\dots S_{H,W}$

出力

迷路から脱出するための最小の移動回数を出力してください。
迷路から脱出できない場合、-1 を出力してください。
最後に改行してください。

サンプル

入力1

3 3
ZDD
ZZZ
DDD

出力1

例えば、→→↓↓←↑↓→ のように移動すると、通ったマスの文字列が ZDDZDDZDD となった状態で右下のマスに到達できるため、脱出することができます。
→→↓↓ でも右下のマスに到達できますが、通ったマスの文字列が ZDDZD となり、ZDD で終わっていないので脱出できません。
また、→→↓↓← は、通ったマスの文字列が ZDDZDD であり、さらにゴールマスを一度通っていますが、現在ゴールマスにいないので脱出できません。

入力2

6 6
ZDDZDD
DZZDDZ
ZDZZZD
ZDZZZZ
DZZDDD
DZDDZD

出力2

Submit

登録なしで提出できます。

Go (1.21)