← 返回题目列表

AtCoder · past202309_k

K. 方形

中文机器翻译题面 查看原题

问题陈述

有一个 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