突然我发现我已经好几天没有走出家门了。我开始担心那天我能否准时出门。这是因为我的房子结构复杂,就像一个迷宫,如果我没有选择正确的路线,就会花费太多时间。我想估算一下比赛当天离开家所需的时间。
此外,我家里有一台笔记本电脑,用于比赛。当然,您必须在领取后才可以离开家。换句话说,我需要找到离开房间、取回电脑并离开家的最短时间。
問題文
座標 (x,y) 信息是 y 线 第 x 第一个字符写的是, 分别为
. : 部屋 # : 壁 C : 計算機がある場所 S : 「僕」の部屋 G : 家の玄関。 “我”是 1 单位时间内的当前位置 从 (x,y) 向北、南、东或西任意方向出发 1 您可以继续。
也就是说, 您可以继续执行(x+1,y),(x-1,y),(x,y+1),(x,y-1) 。然而,目的地的坐标是
# : 壁 である場合には移動できない. C : 計算機がある場所 である場合はそこへ移動した後,計算機を回収したことになる.このとき,回収にかかる時間は無視できる. G : 家の玄関である場合は,もしその時点で計算機を回収していたならゴールとなる.そうでない場合は何も起こらない.创建一个程序,输出“我”离开房间并到达目标所需的最短时间(=带着计算器到达我家的前门)。但是,如果无法到达入口或无法领取计算器, 我希望你输出 -1 。
保证平面图被墙包围。
图 1:输入示例 1 的答案
入力
输入将以以下格式从标准输入提供。
N M
S_{1}
S_{2}
...
S_{N}
- 1 线代表您家的大小 N(5 ≦ N ≦ 500)和 M(5 ≦ M ≦ 500) 由半角空格分隔。
- 2 从行 N+1 行中,M 给出一个字符串。这些是房屋平面图的数据。
- 字符串中出现的字符串为“.”、“#”、“C”、“S”或“G”,其含义如上所述。
- S_{1}和S_{N}不包含“#”以外的任何字符,并且N一行中每个字符串的第一个和最后一个字符必须是“#”。
- 每个字符“C”、“S”和“G”必须是 1 仅出现一个。
出力
但是,如果无法进行此类移动, -1 。
入力例 1
5 5 ##### #S..# #.C.# #..G# #####
出力例 1
4
入力例 2
7 7 ####### #S....# #...#.# #...#C# #...### #G....# #######
出力例 2
16
入力例 3
7 7 ####### #S....# #.###.# #.#C#.# #.###.# #....G# #######
出力例 3
-1
- 由于计算机无法恢复,因此无法实现目标。因此,-1。