AT_abc420_d.[ABC420D] Toggle Maze

有一个 $H$ 行 $W$ 列的网格。用 $(i,j)$ 表示从上到下第 $i$ 行、从左到右第 $j$ 列的格子。每个格子的状态由字符 $A_{i,j}$ 表示，含义如下：

• . ：空格子。
• # ：障碍格子。
• S ：起始格子。
• G ：目标格子。
• o ：开启的门格子。
• x ：关闭的门格子。
• ? ：开关格子。

高桥可以每次从当前位置移动到相邻的格子（上下左右），前提是该格子不是障碍格子也不是关闭的门格子，每次移动算一次操作。

此外，每当他移动到一个开关格子时，所有开启的门格子会变为关闭的门格子，所有关闭的门格子会变为开启的门格子。

请判断他是否可以从起始格子出发到达目标格子。如果可以，输出所需的最小操作次数；否则输出 $-1$。

输入按以下格式从标准输入给出：

$H$ $W$
$A_{1,1}A_{1,2}\cdots A_{1,W}$
$A_{2,1}A_{2,2}\cdots A_{2,W}$
$\vdots$
$A_{H,1}A_{H,2}\cdots A_{H,W}$

如果高桥可以从起始格子到达目标格子，输出最小操作次数；否则输出 $-1$。

样例解释 1

按照 $(1,1) \to (1,2) \to (2,2) \to (1,2) \to (1,3) \to (1,4)$ 的顺序移动，他可以在五次操作内到达目标格子。

样例解释 2

无论如何操作，都无法到达目标格子。因此输出 $-1$。

数据范围

• $1\le H,W \le 500$
• $H$ 和 $W$ 为整数。
• 每个 $A_{i,j}$ 取值为 .、#、S、G、o、x、? 之一。
• $A_{i,j}$ 中 S 和 G 各出现恰好一次。

由 ChatGPT 4.1 翻译