自宅からの脱出

题意翻译

### 题目描述 一张地图用一些字符串来描述。地图上的位置代表对应的平面坐标。 上端表示北方。西北角为坐标 $(1,1)$,东南角为坐标 $(M,N)$。坐标 $(x,y)$ 表示第 $y$ 行的第 $x$ 个字符。 - `.` 空地 - `C` 笔记本电脑 - `S` 出发地 - `G` 门 你可以在 $1$ 个单位时间内从当前位置,移动到 $(x+1,y),(x,y+1),(x-1,y),(x,y-1)$ 中的任意一个。 特别的,还有一些不能移动到的要求: - 不能移动到墙壁(`#`)所在的地方。 - 移动到计算机所在地之后立刻拿上电脑,不用考虑此动作所花的时间。 - 到达家的门口时,如果此时没有拿上笔记本电脑,那么什么也不会发生。 请求出拿上电脑并到达门口的所花的最短时间。 ![](https://cdn.luogu.org/upload/pic/23163.png) ### 输入格式 第一行两个以空格隔开的正整数 $n$ 和 $m$,代表房间的大小为 $n$ 行 $m$ 列。 第二行至第 $n+1$ 行,每行一个字符串,为房间的平面图。 ### 输出格式 输出拿上电脑并到达门口的所花的最短时间。 如果不能达到目标,则输出 `-1`。 ### 数据范围及约定 对于 $100\%$ 的数据,$5\le n\le 500$,$5\le m\le 500$。 保证数据中墙壁围成了一个封闭图形。 保证每行的首字符与末字符都为 `#`。 翻译 by @[159号程序员](https://www.luogu.com.cn/user/334586)

题目描述

[problemUrl]: https://atcoder.jp/contests/wupc2012/tasks/wupc2012_3 僕が入力したパスワードは正しかったようだ.とりあえず,参加資格は剥奪されずに済んだ.しかし,圧縮ファイルを解凍するにはまだしばらく時間が掛かるようだった. ふと,僕はここ数日家から一歩も外に出ていないことに気づいた.そして,当日,時間通りに家から出られるだろうか……と不安になってきた.というのも,僕の家は迷路のように複雑な入り組んだ構造をしており,適切な移動経路を選択しないと時間がかかりすぎてしまうからだ.コンテスト当日までに,家から出るために必要な時間を見積もっておきたい. さらに,僕の家にはコンテストで使うノートブック型計算機がある.家を出るのは,もちろんそれを回収した後でなければならない.つまり,僕の部屋を出て,計算機を回収し,家を出るまでの最短時間を求めておく必要がある. 家の見取り図のデータが文字列で与えられる.見取り図のデータは二次元の座標平面上に表すことができる.見取り図は北を上にして書かれており, 北西端の座標を $ (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 $ を出力せよ.

输入输出格式

输入格式


输出格式


输入输出样例

暂无测试点