深さ優先探索

高桥先生住的小区是长方形的，被划分成一个个格子。高桥先生想从家里去鱼店，高桥先生每次可以走到他前后左右四个格子中的其中一个，但不能斜着走，也不能走出小区。 现在给出地图： ```s```：代表高桥先生的家 ```g```：代表鱼店 ```.```：代表道路 ```#```：代表墙壁 高桥先生不能穿过墙壁。 输入：第一行输入 $n(1\le n\le500)$，$m(1\le m\le500)$ 代表小区的长和宽，接下来 $n$ 行每行 $m$ 个字符，描述小区中的每个格子。 输出：如果高桥先生能到达鱼店，输出 ```Yes```，否则输出 ```No```。

[problemUrl]: https://atcoder.jp/contests/atc001/tasks/dfs_a この問題は、講座用問題です。ページ下部に解説が掲載されています。 高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。 高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ c_{0,0} $ $ c_{0,1} $ $ c_{0,W-1} $ $ c_{1,0} $ $ c_{1,1} $ $ c_{1,W-1} $ : $ c_{H-1,0} $ $ c_{H-1,1} $ $ c_{H-1,W-1} $ - $ 1 $ 行目には、街の南北の長さとして整数 $ H(1≦H≦500) $ と東西の長さとして整数 $ W(1≦W≦500) $ が空白で区切られて与えられる。 - $ 2 $ 行目からの $ H $ 行には、格子状の街の各区画における状態 $ c_{i,j}(0≦i≦H-1,\ 0≦j≦W-1) $ が与えられる。 - $ i $ 行目 $ j $ 文字目の文字 $ c_{i,j} $ はそれぞれ `s`, `g`, `.`, `#` のいずれかで与えられ、座標 $ (j,i) $ が下記のような状態であることを表す。 - `s` : その区画が家であることを表す。 - `g` : その区画が魚屋であることを表す。 - `.` : その区画が道であることを表す。 - `#` : その区画が塀であることを表す。 - 高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。 - 与えられた街の外を通ることはできない。 - `s` と `g` はそれぞれ 1 つずつ与えられる。

塀を $ 1 $ 回も壊さずに、家から魚屋まで辿り着くことができる場合は `Yes`、辿りつけない場合は `No` を標準出力に $ 1 $ 行で出力せよ。

4 5
s####
....#
#####
#...g

No

4 4
...s
....
....
.g..

Yes

10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
###.#.#.#.
#.....#...

No

10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
#.#.#.#.#.
#.....#...

Yes

1 10
s..####..g

No

### 解説 **[深さ優先探索による塗りつぶし](https://www.slideshare.net/secret/lyag9AlTOMIY2J "深さ優先探索による塗りつぶし")** from **[AtCoder Inc.](http://www.slideshare.net/chokudai)** ### Sample Explanation 1 高橋君は、魚屋にたどり着くことができません。