Problem
パル王国の国宝である宝石が盗賊たちに盗まれた。 冒険者のあなたはその噂を聞きつけて盗賊のアジトに向かい、なんとか宝石を取り戻すことが出来た。
ところが、宝石をパル王国の城へ返しに出向いたところ、城の守衛兵から、 「我が王はまだあなたを完全に信用していない。その宝石が本物かどうか怪しいし、そもそも宝石を取り戻したというのがウソで、王の命を狙う盗賊の仲間なのではないか？と疑っておられる。」 といわれた。
あなたは、守衛兵から本当に信頼できる人物かどうか試すための試練を与えられた。試練の内容は、 「城の地下倉庫へ行き指定された場所に宝石を置け。そこに宝石が本物だったときに反応する魔法陣が書かれてある。ただしあなたが怪しい行動を起こさないようにするため、地下倉庫の入り口から指定された場所に向かうまで、守衛兵が言った移動パターンをとってはならない。」 というものだった。
例えば、下図にある地下倉庫の形状、禁止パターンに対し、図にかかれてあるような移動パターンを取ってはならない。移動パターンの一部(赤くハイライトされている)が、禁止パターンの中に含まれるからである。(また、この移動パターンの中の2,3番目の動き「↓↓」も禁止パターンの中に含まれる)
一方、 下図のような移動パターンは、移動パターンのどの部分も禁止パターンの中に含まれないので許される。
入力として、地下倉庫の形状、禁止パターンが与えられる。禁止パターンを取らずに、入り口から魔法陣へ移動するのに最低限必要な移動回数を求めよ。
Input
入力には、地下倉庫の形状と禁止パターンが含まれる。
地下倉庫の形状は、以下のように表される。 まず、二つの整数 N,M が与えられる。それぞれ地下倉庫の行数と列数を意味する。(1 ≤ N,M ≤ 50)
続いて、それぞれM個の文字からなる文字列がN行与えられる。 含まれる文字とその意味は以下の通りである。
文字 意味 S 地下倉庫の入り口。一つの地下倉庫につき必ず一つだけ含まれる。 G 魔法陣。一つの地下倉庫につき必ず一つだけ含まれる。 . 通路。(禁止パターンをとらなければ)通ることが出来る。 # 壁。壁の中を通ることはできない。
次に、禁止パターンが与えられる。禁止パターンは以下のように表される。 まず、一つの整数 P が与えられる。禁止パターンの数を意味する。(0 ≤ P ≤ 10)
続いて、禁止パターンを意味する文字列がP行にわたって与えられる。 禁止パターンに含まれる文字とその意味は以下の通りである。
文字 意味 U ↑の移動。 R →の移動。 D ↓の移動。 L ←の移動。
禁止パターンの長さは1以上、10以下である。 ある禁止パターンが、別の禁止パターンの部分文字列となっていることもある。また、同一の禁止パターンが含まれることもある。
output
最低限必要な移動回数を意味する整数を出力せよ。魔法陣へ辿りつけない場合は -1 を出力せよ。
入出力例
上記入力形式で複数のデータセットが与えられます。各データセットに対して上記出力形式で出力を行うプログラムを作成して下さい。
n, m が 0 のとき入力の終わりを示します。
入力例
7 6 ...... .####. .####. ...S#. ...##. ...##. .....G 3 LD DD LLL 7 8 S#...... .#.####. .#.#G.#. .#.##.#. .#....#. .######. ........ 8 DDDD DDDU UUUU UUUD RRRR RRRL LLLL LLLR 3 8 ######## S......G ######## 2 U D 6 10 .......... .S........ .......... .......... ........G. .......... 0 6 7 ....... ...#... ...#.S. ...###. .G..... ....... 2 LL DD 0 0
出力例
13 60 7 10 -1