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 翻译