A君とB君は、『Changing Grids』というゲームに熱中している。このゲームは2人用で、プレイヤー1がステージを構成し、プレイヤー2がそのステージに挑戦しゴールを目指すというものである。
今、A君とB君はこのゲームを何度かプレイしているが、A君の連勝でB君は1度も勝つことができていない。そこであなたは、B君にこのゲームを攻略するためのヒントを教えてあげることにした。
時刻T0 = 0における縦H×横Wの大きさの二次元グリッドの状態がArea0として与えられる。次に、このグリッドの状態は時刻Tiにおいて、状態Areaiに切り替わる。この切り替わる過程はN回繰り返される。初期状態のグリッドにはスタートの位置'S'とゴールの位置'G'が与えられる。いずれかのグリッドにおいてゴールへ辿り着ける場合は、そのときの最小歩数を出力し、ゴールへ辿り着けない場合は、'-1'を出力せよ。なお、以下の条件も満たす必要がある。
入力は以下の形式で与えられる。
H W Area0 N T1 Area1 T2 Area2 . . TN AreaN
1行目に2つの整数H,Wが空白区切りで与えられる。これは、それぞれ二次元グリッドの縦と横の大きさを表す。2行目からH+1行目までの各行に初期状態の二次元グリッドの状態が与えられる。H+2行目に整数Nが与えられる。これは、二次元グリッドの変化する回数を表す。H+3行目以降にN個の二次元グリッドの切り替わる時刻Tiとその状態が与えられる。ただし、Tiは全て整数である。
入力は以下の条件を満たす。
スタートからゴールへ到達するための最小の歩数を出力せよ。ただし、ゴールに到達できない場合は'-1'を出力せよ。
2 2 S. .G 1 3 ## ##
2
1番目のグリッドに切り替わる時刻T1は3であり、時間内にプレイヤーはスタートからゴールまでの最短歩数が2歩で辿り着くことが可能なので2を出力する。
2 2 S. .G 1 2 ## ##
-1
2 3 S## ##G 4 2 ### .## 3 ### #.# 5 ### ##. 7 ### ###
3
4 3 S.. ... .G. ... 4 2 ### #.# ### #.# 4 ### #.. #.. ### 6 ### #.# ### #.. 8 ### #.. #.. ###
3
3 3 S## ### ##G 1 1 ... ... ...
4