AT_past202309_k.マス目

给定一个 $N \times N$ 的方格。用 $(i,j)$ 表示第 $i$ 行（自上往下）第 $j$ 列（自左往右）的方格。

每个方格有如下四种状态之一：起点、目标、通道和坑洞。第 $(i,j)$ 个方格的状态用 $S_{i,j}$ 表示。

• S 表示该方格是起点。恰好有一个起点。
• G 表示该方格是目标。至少有一个目标点。
• . 表示该方格是通道。
• X 表示该方格是坑洞。

请对于 $k=1,2,\dots,N-1$ 解决如下问题。

你最初位于起点。然后，你可以重复进行如下操作：

• 选择一个方向（上、下、左、右），连续移动 $k$ 格到该方向。

你在执行该操作时，不能经过坑洞方格，也不能移动出网格之外。

问你是否能在某次操作结束时恰好位于目标方格上，如果可以，输出所需的最少操作次数，否则输出 $-1$。

注意，中间经过目标方格但不是操作结束时不计为到达目标。

输入从标准输入读入，格式如下：

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出 $N-1$ 行。

对于 $1 \le i \le N-1$，第 $i$ 行输出 $k=i$ 时到达目标方格所需的最小操作数，如果无法到达则输出 $-1$。

样例解释 1

对于 $k=2$，你可以通过两步操作，到达目标。

• 往下移动，从 $(1,1)$ 到 $(3,1)$。
• 往右移动，从 $(3,1)$ 到 $(3,3)$。

只进行一次移动，不能到达目标，所以答案是 $2$。

注意，对于 $k=3$，如下移动方式不可行：

• 往右移动，从 $(1,1)$ 到 $(1,4)$。

由于此移动路径会经过 $(1,2)$，而这里是坑洞，所以该操作不允许。

数据范围

• $1 \le N \le 1500$
• $S_{i,j}$ 为 S、G、. 或 X
• 恰好有一个 $(i,j)$ 使得 $S_{i,j}=S$
• 至少有一个 $(i,j)$ 使得 $S_{i,j}=G$
• $N$ 为整数。

由 ChatGPT 5 翻译