AT_wupc2012_3.自宅からの脱出

一张地图用一些字符串来描述。地图上的位置代表对应的平面坐标。

上端表示北方。西北角为坐标 $(1,1)$，东南角为坐标 $(M,N)$。坐标 $(x,y)$ 表示第 $y$ 行的第 $x$ 个字符。

• . 空地
• C 笔记本电脑
• S 出发地
• G 门

你可以在 $1$ 个单位时间内从当前位置，移动到 $(x+1,y),(x,y+1),(x-1,y),(x,y-1)$ 中的任意一个。

特别的，还有一些不能移动到的要求：

• 不能移动到墙壁（#）所在的地方。

• 移动到计算机所在地之后立刻拿上电脑，不用考虑此动作所花的时间。

• 到达家的门口时，如果此时没有拿上笔记本电脑，那么什么也不会发生。

请求出拿上电脑并到达门口的所花的最短时间。

第一行两个以空格隔开的正整数 $n$ 和 $m$，代表房间的大小为 $n$ 行 $m$ 列。

第二行至第 $n+1$ 行，每行一个字符串，为房间的平面图。

输出拿上电脑并到达门口的所花的最短时间。

如果不能达到目标，则输出 -1。

对于 $100\%$ 的数据，$5\le n\le 500$，$5\le m\le 500$。

保证数据中墙壁围成了一个封闭图形。

保证每行的首字符与末字符都为 #。

翻译 by @159号程序员