← 返回题目列表

AtCoder · wupc2012_3

C. 离家出走

中文机器翻译题面 查看原题
 看来我输入的密码是正确的。目前,参赛资格并未被取消。不过,解压压缩文件似乎需要一些时间。

 突然我发现我已经好几天没有走出家门了。我开始担心那天我能否准时出门。这是因为我的房子结构复杂,就像一个迷宫,如果我没有选择正确的路线,就会花费太多时间。我想估算一下比赛当天离开家所需的时间。

 此外,我家里有一台笔记本电脑,用于比赛。当然,您必须在领取后才可以离开家。换句话说,我需要找到离开房间、取回电脑并离开家的最短时间。

問題文

 房屋平面图数据以字符串形式给出。平面图数据可以在二维坐标平面上表示。平面图是朝北朝上写的。 西北角坐标 (1,1) ,则东北端的坐标为 (M,1)、东南角坐标为 (M,N) 变为。
座標 (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。