Skip to content

Latest commit

 

History

History
114 lines (90 loc) · 4.41 KB

statement.md

File metadata and controls

114 lines (90 loc) · 4.41 KB
Raw

Description

shiro君はゲームが好きです。shiro君はあるダンジョンをクリアしたいです。そのダンジョンは、縦 $N$ 行、横 $M$ 列のグリッドになっています。
グリッドは、左上のマスが $(1, 1)$ 、右下のマスが $(N, M)$ という座標で表されます。
上から $r$ 行目、左から $c$ 列目のマス目の座標は $(r, c)$ です。

各マスには、"L"、"R"、"U"、"D"、"."のいずれかの半角文字が書かれています。

あなたは最初、$(1, 1)$というマスにいます。次のルールに従ってあなたはマスを移動していきます。

今居るマスが$(r, c)$であるとしたとき、

  • 今居るマスに“L”と書かれていた場合、あなたは$(r, c-1)$に移動します。
  • 今居るマスに“R”と書かれていた場合、あなたは$(r, c+1)$に移動します。
  • 今居るマスに“U”と書かれていた場合、あなたは$(r-1, c)$に移動します。
  • 今居るマスに“D”と書かれていた場合、あなたは$(r+1, c)$に移動します。
  • 今居るマスに“.”と書かれていた場合、あなたは$(r, c-1)、(r, c+1)、(r-1, c)、(r+1, c)$のうち好きなマスに移動することができます。

1マス移動するのに1分かかります。また、移動する際、$N × M$のグリッドの外には出ないように移動するとします。ゴールはマス$(N,M)$で、ゴールにたどり着くことができれば、shiro君はこのダンジョンをクリアできます。

shiro君は完璧主義なので、できるだけ少ない移動時間でこのダンジョンをクリアしようと考えました。

この時、マス$(N,M)$へ移動するのにかかる最短時間(分)を出力してください。ただし、どのように移動してもマス$(N,M)$にたどり着けずダンジョンがクリアできない場合、“kusoge-“と出力してください。

Constraints

  • $N, M$は整数
  • $g_{ij} (1 \leq i \leq N, 1 \leq j \leq M)$ は $(i, j)$ のマスに書かれている文字を表し、“L”, “R”, “U”, “D”, “.”のいずれかある。
  • $(1, i) (1 \leq i \leq M)$に“U”が書かれることはない。
  • $(i, 1) (1 \leq i \leq N)$に“L”が書かれることはない。
  • $(i, M) (1 \leq i \leq N)$に“R”が書かれることはない。
  • $(N, i) (1 \leq i \leq M)$に“D”が書かれることはない。

Small

  • $T = 5$
  • $1 \leq N, M \leq 5$

Large

  • $T = 50$
  • $1 \leq N, M \leq 20$

Input

1つの入力ファイルは複数のテストケースからなる。

入力ファイルの最初の一行目にはテストケースの個数$T$が記される。

2行目以降には、$T$ 個のテストケースが記述されており、各テストケースは次の形式で表される。

$N$ $M$
$g_{11} g_{12} \ldots g_{1M}$
$g_{21} g_{22} \ldots g_{2M}$
$\ldots$
$g_{N1} g_{N2} \ldots g_{NM}$

Output

各テストケースに対して、ダンジョンをクリアするのにかかる最短時間(分)を1行ずつ出力せよ。

Sample Input

3
4 4
.D..
.RD.
DL.L
RRR.
2 2
..
..
2 3
RRL
U..

Sample Output

6
2
kusoge-

入力例は3つのテストケースからなります。

1つめのテストケース

例えば以下のようなルートがあります。
$(1,1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)　\rightarrow (4, 3) \rightarrow (4, 4)$
通ったマスに訪れた時刻を記入すると、以下のようになります。

01..
.23.
DL4L
RR56

移動時間は6分で、これが最短です。この他にも、
$(1,1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (4, 1) \rightarrow (4, 2) \rightarrow (4, 3) \rightarrow (4, 4)$
というルートも移動時間は6分です。

0D..
1RD.
2L.L
3456

2つめのテストケース

今回のケースのように、“L”, “R”, “U”, “D”からなるマスが1つも存在しないパターンもあります。

3つめのテストケース

このケースでは、
$(1,1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (1, 2) \rightarrow (1, 3)\ldots$
のように、 $(1, 3)$ と $(1, 2)$ を行き来し続けることになり、ループしてしまいます。
よって、ゲームをクリアすることができないため、クソゲーです。
"kusoge-"と出力しましょう。