/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
H 行 W 列のグリッドがあります。上から i 行目、左から j 列目のマス目を (i,j) と表します。各マスの状態は文字 A_{i,j} で表され、意味は以下の通りです。
.：空きマス。#：障害物マス。S：スタートマス。G：ゴールマス。o：開いたドアのマス。x：閉じたドアのマス。?：スイッチマス。
高橋君は、 1 回の操作で今いるマスから上下左右に隣り合う、障害物マスでも閉じたドアでもないマスへ移動することができます。
また、スイッチマスに移動する度に全ての開いたドアのマスは閉じたドアのマスに、閉じたドアのマスは開いたドアのマスに変わります。
高橋君がはじめスタートマスにいる状態からゴールマスにいる状態にするよう操作できるか判定し、可能な場合は必要な操作回数の最小値を求めてください。
制約
- 1\le H,W \le 500
- H,W は整数
- A_{i,j} は
.,#,S,G,o,x,?のいずれか SとGは A_{i,j} にそれぞれちょうど 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
2 4 S.xG #?o.
出力例 1
5
(1,1) から順に (1,2),(2,2),(1,2),(1,3),(1,4) と移動するよう操作することで 5 回の操作でゴールマスにいる状態にすることができます。
入力例 2
1 5 So?oG
出力例 2
-1
どのように操作してもゴールマスにいる状態にすることはできません。したがって、 -1 を出力してください。
入力例 3
5 5 Sx?x? o#o#x ?o?o? x#x#o ?x?oG
出力例 3
10
Score : 400 points
Problem Statement
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.
Constraints
- 1\le H,W \le 500
- H and W are integers.
- Each A_{i,j} is one of
.,#,S,G,o,x,?. SandGeach appear exactly once in A_{i,j}.
Input
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}
Output
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 Input 1
2 4 S.xG #?o.
Sample Output 1
5
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 Input 2
1 5 So?oG
Sample Output 2
-1
No matter how he operates, he cannot reach the goal cell. Therefore, output -1.
Sample Input 3
5 5 Sx?x? o#o#x ?o?o? x#x#o ?x?oG
Sample Output 3
10