← 返回题目列表

AtCoder · abc420_d

G. 切换迷宫

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有一个网格 H 行和 W 列。让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。每个单元格的状态由一个字符表示 A_{i,j},含义如下:

  • . :空单元格。
  • # :障碍细胞。
  • S :启动单元格。
  • G :目标单元格。
  • o :打开单元门。
  • x :牢房门关闭。
  • ? :切换单元格。

高桥可以在一次操作中从当前单元格移动到既不是障碍单元格也不是关门单元格的相邻单元格(上、下、左、右)。

此外,每次他移动到开关牢房时,所有开门牢房都会变成关门牢房,所有关门牢房都会变成开门牢房。

确定他是否可以从起始单元格的初始状态移动到目标单元格,如果可能,找到所需的最少操作数。

约束

  • 1\le H,W \le 500
  • H 和 W 是整数。
  • 每个 A_{i,j} 是其中之一 ., #, S, G, o, x, ?.
  • S 和 G 每个都恰好出现一次 A_{i,j}.

输入

输入由标准输入按以下格式给出:

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) to (1,2),(2,2),(1,2),(1,3),(1,4) 按照这个顺序,他可以通过五次操作到达目标单元格。


示例输入 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