AT_abc387_d [ABC387D] Snaky Walk

有一个 $H$ 行 $W$ 列的网格。从上往下第 $i$ 行、从左往右第 $j$ 列的单元格记为 $(i,j)$。 每个单元格是起点、终点、空单元格或障碍物，这些信息由 $H$ 个长度为 $W$ 的字符串 $S_1,S_2,\dots,S_H$ 表示。具体来说，当 $S_i$ 的第 $j$ 个字符是 `S` 时，单元格 $(i,j)$ 是起点；是 `G` 时是终点；是 `.` 时是空单元格；是 `#` 时是障碍物。保证起点和终点各恰好存在一个。 你现在位于起点。你的目标是通过重复移动到当前单元格边相邻的单元格，最终到达终点。但有以下限制：不能移动到障碍物或网格外，且必须交替进行纵向移动和横向移动（首次移动方向可任选）。 请判断能否到达终点，若可能则求出移动次数的最小值。 更形式化地说，请判断是否存在满足以下所有条件的单元格序列 $(i_1,j_1),(i_2,j_2),\dots,(i_k,j_k)$，若存在则求 $k-1$ 的最小值： - 对所有 $1 \leq l \leq k$，满足 $1 \leq i_l \leq H$ 且 $1 \leq j_l \leq W$，且 $(i_l,j_l)$ 不是障碍物 - $(i_1,j_1)$ 是起点 - $(i_k,j_k)$ 是终点 - 对所有 $1 \leq l \leq k-1$，满足 $|i_l - i_{l+1}| + |j_l - j_{l+1}| = 1$ - 对所有 $1 \leq l \leq k-2$，若 $i_l \neq i_{l+1}$，则 $i_{l+1} = i_{l+2}$ - 对所有 $1 \leq l \leq k-2$，若 $j_l \neq j_{l+1}$，则 $j_{l+1} = j_{l+2}$

输入通过标准输入给出，格式如下： > $H$ $W$ > $S_1$ > $S_2$ > $\vdots$ > $S_H$

若可以到达终点，输出移动次数的最小值；否则输出 `-1`。

### 约束条件 - $1 \leq H, W \leq 1000$ - $H, W$ 是整数 - $S_i$ 是由 `S`、`G`、`.`、`#` 组成的长度为 $W$ 的字符串 - 起点和终点各恰好存在一个 ### 样例解释 1  按照左图的路径 $(1,2) \rightarrow (2,2) \rightarrow (2,3) \rightarrow (3,3) \rightarrow (3,4) \rightarrow (2,4) \rightarrow (2,5) \rightarrow (1,5)$，可以通过 7 次移动到达终点。无法用 6 次或更少移动到达终点，因此答案是 7。注意右图所示的连续横向移动（或连续纵向移动）路径是不被允许的。 ### 样例解释 2 无法到达终点。 翻译由 DeepSeek R1 完成