0731 - Human_Frog

前置き

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

問題

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

追伸

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