0731 - Human_Frog

時間制限 3 秒 / メモリ制限 128 MB / 得点 1 / Writer ei1612 / x 11 / 統計 /


TLE
3sec
MLE
128MB
得点
1

前置き

あなたは、魔法使い Time_Shuck先輩によってカエルに姿をかえられてしまった!(なんてこった)。しかし、 魔法使いTime_Shuck先輩の私物を盗んで脅迫すれば、カエルから人間に姿を戻してくれるかもしれない。
かくしてあなたは、脅迫材料を探しにいくのであった...。

問題

最初にHとWとNが与えられる。Hはマップの高さ、Wはマップの横幅、Nは脅迫材料の数である。 脅迫材料は1〜Nの数字がふられており、それぞれ番号通りに脅迫材料をとらなければならない。
マップでは、スタート地点は'S',壁は'#',何もないマスは'.'である。 もちろん脅迫材料は1~Nの数字である。
そして何より、あなたはカエルだ。人権のないただのカエルなのである。
カエルはジャンプしかできないため、移動できる場所が人間と異なっている。
. . . . .
. . . . .
. . S . .
. . . . .
. . . . .
というマップがあった場合、カエルが動けるのは、
. * * * .
* . . . *
* . S . *
* . . . *
. * * * .
という、アスタリスクにした部分である。まあ、要するに自分のいる位置から、
①上に2マス進んだところとその両脇2マス
②下に2マス進んだところとその両脇2マス
③右に2マス進んだところとその上下2マス
④左に2マス進んだところとその上下2マス
である。 またすべての材料をあつめられなかったら、"YOU MUST SYU-CHING!" を出力せよ。

入力

 H W
 N
 map[0][0] map[0][1] ... map[0][W-1]
 ...
 ...
 map[H-1][0] map[H-1][1]... map[H-1][W-1]

1行目に整数 H W が空白区切りで与えられる。

2行目に整数 N が与えられる。

3 行目から3+H行にかけてマップが空白区切りで与えられる。

出力

ゴールに行ける場合の最短時間を出力せよ。
ゴールできない場合は、"YOU MUST SYU-CHING!"と出力せよ。
出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

  • 1 ≦ H, W ≦ 100
  • 1 ≦ N < 10

  • 制約がまちがっていました。すみません。

入出力例

入力例1

1 5
1
1 . . S .

出力例1

YOU MUST SYU-CHING!

入力例2

3 4
2
1 . . .
. . S .
. . 2 .

出力例2

3

追伸

昨日1時間で作ったので間違いがあったらすみません。問題文が薄いのもすべてそのせいです。
あと、某Tなんちゃら先輩とはなんの関係もありません。