K - Grid Editorial /

Time Limit: 8 sec / Memory Limit: 1024 MB

問題文

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 回連続で移動する。

ただし、操作によって穴のマスを通過することや、マス目の外に出ることは許されません。

操作が終わったあとにゴールのマスにいる状態にすることができるか判定し、できるのであれば必要な操作の回数の最小値を求めてください。

なお、移動中にゴールを通過しても、ゴールのマスにいる状態になったとはみなさないことに注意してください。

制約

  • 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 は整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
S_1
S_2
\vdots
S_N

出力

N-1 行出力せよ。

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

入力例 1

5
SX...
.....
..GX.
..XG.
X.X.G

出力例 1

4
2
-1
-1

k=2 のとき、以下のように操作をすることで 2 回で操作が終わったあとにゴールのマスにいる状態にすることができます。

  • 下を選ぶ。(1,1) から (3,1) に移動する。
  • 右を選ぶ。(3,1) から (3,3) に移動する。

1 回の移動で操作が終わったあとにゴールのマスにいる状態にすることはできないので、答えは 2 です。

k=3 のとき、以下のような操作はできないことに注意してください。

  • 右を選ぶ。(1,1) から (1,4) に移動する。

この操作は、操作中に穴であるマス (1,2) を通過しているため許されません。

入力例 2

2
GX
XS

出力例 2

-1

Problem Statement

There is an N \times N grid. Let (i,j) denote the square at the i-th row from the top and j-th square from the left.

Each square is one of the following: the starting point, a goal, a passage, and a hole. The state of the square (i,j) is given as S_{i,j}.

  • S indicates that the square is the starting point. There is exactly one starting point.
  • G indicates that the square is a goal. There is one or more goals.
  • . indicates that the square is a passage.
  • X indicates that the square is a hole.

Solve the following problem for k=1,2,\dots,N-1.

You are initially at the starting square. Then, you repeat the following operation.

  • Choose one of the four directions: up, down, left, right. Move k squares consecutively in the chosen direction.

You may not pass through a hole square or exit the grid by the operation.

Determine if you can be at a goal square at the end of an operation, and if so, find the minimum number of operations required to do so.

Note that passing through a goal in the middle of an operation does not count as finishing at a goal square.

Constraints

  • 1 \le N \le 1500
  • S_{i,j} is S, G, ., or X.
  • There is exactly one pair (i,j) such that S_{i,j}=S.
  • There is one or more pairs (i,j) such that S_{i,j}=G.
  • N is an integer.

Input

The Input is given from Standard Input in the following format:

N
S_1
S_2
\vdots
S_N

Output

Print N-1 lines.

For 1 \le i \le N-1, the i-th line should contain the minimum number of operations required to be at a goal square at the end of an operation for k=i if it is possible to do so, and -1 otherwise.

Sample Input 1

5
SX...
.....
..GX.
..XG.
X.X.G

Sample Output 1

4
2
-1
-1

For k=2, you can perform two operations as follows to be at the goal square at the end of an operation.

  • Choose down. Move from (1,1) to (3,1).
  • Choose right. Move from (3,1) to (3,3).

With just one operation, you cannot be at a goal square at the end of an operation, so the answer is 2.

Note that for k=3, the operation cannot be performed as follows.

  • Choose right. Move from (1,1) to (1,4).

This operation is not allowed because it passes through (1,2), which is a hole.

Sample Input 2

2
GX
XS

Sample Output 2

-1