あらすじ
試合を終えて家路へ向かうサッカー部員たち。
疲れからか、不幸にも黒塗りの高級車に追突してしまう。
後輩をかばい全ての責任を負った三浦に対し、車の主、暴力団員谷岡に言い渡された示談の条件とは——
問題
家路につくサッカー部員たちは一刻も早く寝たいため家までの最短経路を知りたい。
ただ、彼らはサッカー部員でありプログラムなど微塵もわからないため、
代わりに黒塗りの高級車に追突せずに帰宅できる最短経路を出力するプログラムを作ってあげよう。
ただし、黒塗りの高級車の方が家より近い場合、たまげる運命は回避出来ない。
入力
h w c[0][0] ... c[0][w-1]:
:
:
c[h-1][0] ... c[h-1][w-1]
1 行目に縦の長さ h と横の長さ w が与えられる。
その後 h 行に渡りマップの状態 c[0][0] から c[h-1][w-1]が与えられる。
'S' は現在地、 'G'は家、 '@' は黒塗りの高級車、 '#' は建物、 '.' は道を表す。
出力
家の方が近い場合は家までの最短経路を、黒塗りの高級車の方が近い場合は"Tamagetana"を、
どちらにもたどり着けない場合は"Tamagenai"を出力せよ。
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- 0 ≦ h, w ≦ 100000
- 0 ≦ h * w ≦ 100000
- 家と黒塗りの高級車は現在地からの距離が等しくならない。
入出力例
入力例1
5 5 #...# #.#.# ..#.# .#..# S#..G
出力例1
12
入力例2
5 5 #...# #.#.# ..#.# .#@.# S#..G
出力例2
Tamagetana
解説
家より黒塗りの高級車の方が近いため"Tamagetana"を出力する。