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