AT_abc420_d [ABC420D] Toggle Maze

There is a grid with $ H $ rows and $ W $ columns. Let $ (i,j) $ denote the cell at the $ i $ -th row from the top and $ j $ -th column from the left. The state of each cell is represented by a character $ A_{i,j} $ , with the following meanings: - `.` : Empty cell. - `#` : Obstacle cell. - `S` : Start cell. - `G` : Goal cell. - `o` : Open door cell. - `x` : Closed door cell. - `?` : Switch cell. Takahashi can move from his current cell to an adjacent cell (up, down, left, right) that is neither an obstacle cell nor a closed door cell in one operation. Also, every time he moves to a switch cell, all open door cells become closed door cells, and all closed door cells become open door cells. Determine whether he can move from the initial state of being at the start cell to being at the goal cell, and if possible, find the minimum number of operations required.

The input is given from Standard Input in the following format: > $ 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} $

If Takahashi can move from the initial state of being at the start cell to being at the goal cell, output the minimum number of operations required; otherwise, output $ -1 $ .

### Sample Explanation 1 By moving from $ (1,1) $ to $ (1,2),(2,2),(1,2),(1,3),(1,4) $ in that order, he can reach the goal cell in five operations. ### Sample Explanation 2 No matter how he operates, he cannot reach the goal cell. Therefore, output $ -1 $ . ### Constraints - $ 1\le H,W \le 500 $ - $ H $ and $ W $ are integers. - Each $ A_{i,j} $ is one of `.`, `#`, `S`, `G`, `o`, `x`, `?`. - `S` and `G` each appear exactly once in $ A_{i,j} $ .