问题陈述
有一个 N \times N 网格。让 (i,j) 表示 i从顶部开始的第行和 j从左边算起第一个方格。
每个方格都是以下之一:起点、目标、通道和洞。广场的状态 (i,j) 给出为 S_{i,j}.
S表示该正方形是起点。只有一个起点。G表示该方块是球门。有一个或多个目标。.表示该方块是一个通道。X表示该正方形是一个洞。
解决以下问题 k=1,2,\dots,N-1.
您最初位于起始广场。然后,重复以下操作。
- 选择四个方向之一:上、下、左、右。移动 k 沿所选方向连续排列。
您不能通过该操作穿过洞格或退出网格。
确定您是否可以在操作结束时到达目标方格,如果可以,请找到完成此操作所需的最少操作数。
请注意,在操作过程中穿过球门不算作在球门格处完成。
约束
- 1 \le N \le 1500
- S_{i,j} is
S,G,.,或X. - 正好有一对 (i,j) 这样 S_{i,j}=
S. - 有一对或多对 (i,j) 这样 S_{i,j}=
G. - 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,您可以执行如下两个操作,以便在操作结束时到达目标方格。
- 选择向下。移自 (1,1) to (3,1).
- 选择正确。移自 (3,1) to (3,3).
仅通过一次操作,您就无法在操作结束时到达目标方格,因此答案是 2.
请注意,对于 k=3,无法执行如下操作。
- 选择正确。移自 (1,1) to (1,4).
不允许此操作,因为它通过 (1,2),这是一个洞。
示例输入 2
2 GX XS
示例输出 2
-1