008 - 一方通行迷路ゲーム

問題

あなたは一方通行迷路ゲームというコンピュータゲームで遊んでいる。このゲームでは、H行W列のマスで区切られた長方形が画面上に表示される。各マスは壁、道、スタート、ゴールのいずれかで、スタートとゴールはそれぞれ一つだけである。道のマスとスタートのマスでは、上下左右に隣接する道のマスかゴールのマスだけに進むことができる。ただし、道のマスのうちいくつかは一方通行のマスであり、上下左右のうち一つの方向にしか出られない。

1回のゲームでは、スタートから出発して道を通ってゴールを目指す。ゴールにたどりつければゲームクリア、たどりつけないことがわかった時点でゲームオーバーである。スタートからゴールまでの移動回数が少ないほど、ランキングが上がる。ゲーム中で一度だけ、一方通行のマスを一つ選んでその方向を好きな方向に変えることができる。ランキング上位を目指すために、あなたは画面をよく見て、どの一方通行のマスを選んで方向を変えればいいか、よく検討しなければならない。

画面上に各マスの情報が与えられたとき、スタートからゴールにたどりつけるかどうか判定し、たどりつけるときは最小の移動回数を報告するプログラムを作成せよ。

入力

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

$H$ $W$
s1,1 s1,2...s1,W
s2,1 s2,2...s2,W
:
sH,1 sH,2...sH,W

1行目に画面上の長方形の行の数$H(2 \leq H \leq 300)$、列の数$W(2 \leq W \leq 300)$が与えられる。続く$H$行に$i$行目のマスを表す文字s_i,jが与えられる。各s_i,jは以下のどれか一つである。

.	一方通行ではない道
#	壁
U,D,L,R	一方通行の道。それぞれ上、下、左、右の方向へだけでられるマスを表す。
S,G	Sがスタート、Gがゴール

出力

スタートからゴールにたどりつく最小の移動回数を1行に出力する。ただし、たどりつけないときは「-1」を出力する。  

入出力例

入力例1

4 5
##S##
#..##
#.DG.
#..##

出力例1

3

入力例2

4 3
#S.
#U.
GD.
###

出力例2

5

入力例3

3 4
#..#
.LDG
.S#.

出力例3

-1