Mujin Programming Challenge 2018

E - 迷路


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 1024MB

配点 : 500

問題文

NM 列のマス目があります。上から i 行目、左から j 列目にあるマスを (i,j) で表します。 特に、左上のマスは (1,1) であり、右下のマスは (N,M) です。

マス目の状態は 二次元配列 s で表され、s_{ij}# のときマス (i,j) には障害物があり、. または S または G のとき障害物はありません。

ロボットは 0 秒にS のマスから スタートし、 G のマスに出来るだけ短い時間で辿り着こうとします。

しかしロボットは常にどの方向にも動けるというわけではありません。

長さ K の文字列 d が与えられます。毎秒、ロボットは隣接するマスに移動するか、今いるマスにとどまることができます。ただし、t 秒後から t+1 秒後にかけては、tK で割った余りを r (0 \leq r \leq K-1) として、 d_{r+1} の方向にのみ 1 秒かけて 1 マス進むことが出来ます。現在いるマスを (i,j) とした時、d_{r+1}U の場合は (i-1,j) に、 D の場合は (i+1,j) に、L の場合は (i,j-1) に、 R の場合は (i,j+1) に移動できます。マス目の外に出るような移動や、障害物があるマスへの移動は出来ません。

この条件のもとで S からG のマスに辿り着くまでの最短の時間を求めてください。

制約

  • 2 \leq N,M \leq 1000
  • 1 \leq K \leq 100000
  • s# または . または S または G からなる
  • SG の書かれたマスはそれぞれ 1 つずつ存在する
  • d の長さは K
  • dU または D または L または R からなる
  • N,M,K は整数である

入力

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

N M K
d_{1}...d_{K}
s_{11}...s_{1M}
:
s_{N1}...s_{NM}

出力

ロボットが S から G まで移動するのにかかる最短の時間を出力せよ。ただし、どのように移動しても S から G まで移動出来ない場合は -1 を出力せよ。


入力例 1

2 3 5
UDRRL
S..
.#G

出力例 1

7

入力例 2

3 3 5
UDUDD
S..
...
.G.

出力例 2

-1

どのように移動しても 2 列目に移動出来ません。


入力例 3

3 3 5
UDLRD
S..
.#.
..G

出力例 3

12

Submit提出する