B問題 - Making Dango

実行時間制限: 2 sec / メモリ制限: 1024 MB

問題文

C君は工学部団子が大好きです。工学部団子は工学部員の顔が描かれた団子を順番に串に刺すことで作ることが出来ます。

そのため次のような方法で工学部団子を作ろうとしています。

• グリッド上のスタート地点から、壁ではない上下左右に隣接する(マンハッタン距離が\(1\)である)マスを通り移動する。
• chihi311,Licht12,dangonoyousei,Zero_cola,Rencoda3が書かれた団子があるマスを順に通る。
• \(5\)人の部員の書かれた団子があるマスを通った後、ゴール地点に行く。

\(H\)列\(W\)行のグリッドは「団子、壁、スタート、ゴール、空きマス」のいずれかです。\(i(1 \leq i \leq H)\)行目\(j(1 \leq j \leq W)\)列目の情報\(c_{i,j}\)は.,#,S,G,C,D,L,R,Zの\(9\)種類の文字によって与えられて、それぞれマス\((i,j)\)が以下の状態であることを表している。

• \(c_{i,j}=\).のとき、マス\((i,j)\)は空きマスである。
• \(c_{i,j}=\)#のとき、マス\((i,j)\)は壁である。
• \(c_{i,j}=\)Sのとき、マス\((i,j)\)はスタート地点である。またそのようなマスは1マスである。
• \(c_{i,j}=\)Gのとき、マス\((i,j)\)はゴール地点である。またそのようなマスは1マスである。
• \(c_{i,j}=\)Cのとき、マス\((i,j)\)にはchihi311の顔が描かれた団子がある。
• \(c_{i,j}=\)Dのとき、マス\((i,j)\)にはdangonoyouseiの顔が描かれた団子がある。
• \(c_{i,j}=\)Lのとき、マス\((i,j)\)にはLicht12がの顔描かれた団子がある。
• \(c_{i,j}=\)Rのとき、マス\((i,j)\)にはRencoda3の顔が描かれた団子がある。
• \(c_{i,j}=\)Zのとき、マス\((i,j)\)にはZero_colaの顔が描かれた団子がある。
• スタート地点とゴール地点、団子が置かれているマスは空きマスとして扱うことが出来ます。

このとき、C君が工学部団子を作る操作を完了するために移動する回数の最小値を求めよ。もし完成させることができないならば\(-1\)を出力せよ。

制約

• \(1 \leq H,W\)
• \(H \cdot W \leq 2 \cdot 10 ^ 5\)
• \(c_{i,j}\)は.,#,S,G,C,D,L,R,Zのいずれか
• \(c_{i,j}=\)Sである\(i,j\)は\(1\)組
• \(c_{i,j}=\)Gである\(i,j\)は\(1\)組

入力

入力は以下の形式で与えられる。

H W
c_{1,1} c_{1,2} ... c_{1,W} 
c_{2,1} c_{2,2} ... c_{2,W}
...
c_{H,1} c_{H,2} ... c_{H,W}

出力

標準出力に一行で出力してください

入出力例

入力例1

5 5
S#...
..C#.
##LRG
C#DZ#
CCCC#

出力例1

8

• (0,0),(1,0),(1,1),(1,2),(2,2),(3,2),(3,3),(2,3),(2,4)の順で移動すれば8回の移動で工学部団子を作ることができます。

入力例2

5 5
##S##
#...#
.....
#...#
####G

出力例2

-1

そもそも団子がない場合もあります。 またゴールにたどり着けない場合もあります。

入力例3

5 5 
S.R.#
##Z##
##D##
##L##
#.C.G

出力例3

16

団子がおいてあるマスや、スタート、ゴール地点は空マスとしても扱えます。