問題
AUOは最近、Y●utubeでキヨシ・うしざま・ガッチマソ・華声氏による「14th土曜日」の実況動画を視聴することにハマっている。
AUOは「自分もプレイしてみよう」と思ったものの、毎回ジョイソンに速攻で見つかり、一番最初にやられてしまっていた。そこでAUOはジョイソンに見つからずに目的地まで行く練習をするためのゲームを作ることにした。
入力
h w s0 0・・・s0 w-1 : : : sh-1 0・・・sh-1 w-1
1 行目に縦幅を表す整数 h と、横幅を表す整数 w が与えられる。
2 行目以降にマップを表す文字列 s が与えられる。
'S' は自分の位置、 'J' はジョイソンの位置、 'G' は目的地、 '#' は壁、 '.' は道を表す。
出力
ジョイソンに見つからずに自分の位置から目的地まで行けるかどうかを判断し、行ける場合は "Survive" 、そうでなければ "Dead" を出力せよ。(自分は上下左右の四方向にしか移動できない)
なお、ジョイソンがいる場所の縦横一直線上を通ると見つかってしまうので、自分とジョイソンの間に壁がなければそこを通ることはできない。(ジョイソンは移動しない)
出力の最後に改行を忘れずに。
制約
全ての入出力ケースについて以下を満たす。
- 2 ≦ h , w ≦ 20
- 入力される自分の位置はジョイソンの縦横一直線上ではない。
入出力例
入力例1
5 5 S.... ..... ...#J ..... G....
出力例1
Survive
入力例2
10 10 ..S....... .########. ....J..... .########. .########. .......... ##.#....## ..G....... .......... ##########
出力例2
Dead
入力例3
5 5 S.... ..... ..... ..... G...J
出力例3
Survive
ジョイソンに見つかってはいるが、目的地に行くことはできているため "Dead" ではない。