题目详情
返回题库题目描述
有一个 $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\le H,W \le 500$
$H$ 和 $W$ 为整数。
每个 $A_{i,j}$ 取值为 `.`、`#`、`S`、`G`、`o`、`x`、`?` 之一。
$A_{i,j}$ 中 `S` 和 `G` 各出现恰好一次。
输出描述
如果高桥可以从起始格子到达目标格子，输出最小操作次数；否则输出 $-1$。
提示
样例解释 1
按照 $(1,1) \to (1,2) \to (2,2) \to (1,2) \to (1,3) \to (1,4)$ 的顺序移动，他可以在五次操作内到达目标格子。
样例解释 2
无论如何操作，都无法到达目标格子。因此输出 $-1$。