AT_past202309_k マス目

$ N \times N $ のマス目があります。上から $ i $ 番目、左から $ j $ 番目のマスを マス $ (i,j) $ と呼ぶこととします。 それぞれのマスは、スタートかゴールか通路か穴のマスのいずれかです。マス $ (i,j) $ の状態は $ S_{i,j} $ によって与えられます。 - `S` はそのマスがスタートであることを示します。スタートはただ $ 1 $ 個のみ存在します。 - `G` はそのマスがゴールであることを示します。ゴールは $ 1 $ 個以上存在します。 - `.` はそのマスが通路であることを示します。 - `X` はそのマスが穴であることを示します。 $ k=1,2,\dots,N-1 $ に対して、以下の問題を解いてください。 始め、あなたはスタートのマスにいます。その後、以下の操作を繰り返します。 - 上下左右の $ 4 $ 方向のうち、いずれかの方向を選ぶ。選んだ方向に $ k $ 回連続で移動する。 ただし、操作によって穴のマスを通過することや、マス目の外に出ることは許されません。 操作が終わったあとにゴールのマスにいる状態にすることができるか判定し、できるのであれば必要な操作の回数の最小値を求めてください。 なお、移動中にゴールを通過しても、ゴールのマスにいる状態になったとはみなさないことに注意してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

$ N-1 $ 行出力せよ。 $ 1 \le i \le N-1 $ に対して、 $ i $ 行目には $ k=i $ のときに操作が終わったあとにゴールのマスにいる状態にすることができるのであれば必要な操作の回数の最小値を、そうでないのであれば `-1` を出力せよ。

### Sample Explanation 1 $ k=2 $ のとき、以下のように操作をすることで $ 2 $ 回で操作が終わったあとにゴールのマスにいる状態にすることができます。 - 下を選ぶ。 $ (1,1) $ から $ (3,1) $ に移動する。 - 右を選ぶ。 $ (3,1) $ から $ (3,3) $ に移動する。 $ 1 $ 回の移動で操作が終わったあとにゴールのマスにいる状態にすることはできないので、答えは $ 2 $ です。 $ k=3 $ のとき、以下のような操作はできないことに注意してください。 - 右を選ぶ。 $ (1,1) $ から $ (1,4) $ に移動する。 この操作は、操作中に穴であるマス $ (1,2) $ を通過しているため許されません。 ### Constraints - $ 1 \le N \le 1500 $ - $ S_{i,j} $ は `S`,`G`,`.`,`X` のいずれかである。 - $ S_{i,j}= $ `S` である $ (i,j) $ はただ $ 1 $ 個存在する。 - $ S_{i,j}= $ `G` である $ (i,j) $ は $ 1 $ 個以上存在する。 - $ N $ は整数である。