※ この問題には厨二成分が多く含まれます。胸焼けにご注意ください。
ついに復活を遂げた魔王は、再び世界を闇に包むために人間界に攻め入ろうとしていた。
魔王は、本格的な侵攻を始める前に、まず伝説の剣を破壊することにした。 前回の戦争において、魔王は伝説の剣を持つ勇者によって倒された。 魔王の体は闇の衣によって守られているため、生半可な攻撃では魔王を傷つけることはできない。 しかし、伝説の剣は、神々の加護により、魔王の闇の衣すら容易に貫いてしまう。 そのため、今回の戦争に勝利するためには、なんとしてもその伝説の剣を手に入れて破壊する必要がある。
調査の末、伝説の剣はとある遺跡の最奥に安置され、次代の勇者が現われるのを待っていることがわかった。 伝説の剣は、邪悪な者や盗賊によって奪われるのを防ぐために、周囲に点在する無数の宝珠によって封印されている。 魔王は、強力な魔力を持っているため、触れるだけで宝珠を破壊することができる。 ただし、宝珠による封印は多重構造になっており、表層から順に破壊していく必要がある。 例えば、第1の封印の宝珠を破壊する前に第2以降の封印の宝珠に触れたとしても、破壊することはできない。 また、複数の宝珠が同じ封印を構成していることもあるが、魔王はそのうちの一つに触れるだけで、同時にその封印を破壊することができる。
遺跡には神聖な力が満ちており、並の魔物では入ることすらままならない。 そこで、魔王自ら赴き伝説の剣を回収してくることになった。 いかに魔王といえど、長時間その力を受け続ければただではすまない。 魔王の右腕であるあなたの仕事は、念のため魔王が全ての封印を破壊し、伝説の剣の下に辿りつくまでの時間を求めることである。
入力は、複数のデータセットからなり、入力の終わりはスペースで区切られたゼロ二つからなる行である。 データセットの総数は50以下である。 各データセットは、次の形式をしている。
w h s(1,1) ... s(1,w) s(2,1) ... s(2,w) ... s(h,1) ... s(h,w)
wとhは、それぞれ遺跡のフロアを表現する行列データの幅と高さを示す整数であり、それぞれ1 ≤ w, h ≤ 100であり、2 ≤ w + h ≤ 100と仮定して良い。 続くh行はそれぞれ、スペースで区切られたw個の文字から構成されており、文字s(y,x)は、座標(y,x)の地点の状態を示す。
その意味は、以下の通りである。
各データセットに対して、魔王が全ての封印を破壊し、伝説に剣に辿りつくために必要な最短時間を出力せよ。
10 10 S . . . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 . . . . . . . . . . . . . . . . . 4 . . . . . . . . . . . . . . 2 . . . . . . . . G 10 10 S . . . . . 3 . . . . . 3 . . . . . . . . . . . 1 . . . . . . . . . . . 4 . . . . . 3 . . . 1 . . . . . . . . . . 3 . . . . . . . . . . . . . . . . . 4 . . . . . . . . . 5 . . . . 2 . . . . . . . . G 10 10 S . . . . . . . . 1 . . . . . 5 . . . . . 4 . . . . . . . . . . . . 8 . 9 . . . . . . . 10 . . . . . . . 7 . G . . . . . . . . 11 . . . . . . 3 . . . . . . . . 6 . . . . . . . 2 . . . . . . . . . . . . 0 0
38 36 71