A - 深さ優先探索 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

この問題は、講座用問題です。ページ下部に解説が掲載されています。

高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。

高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。

入力

入力は以下の形式で標準入力から与えられる。

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 行で出力せよ。

解説

入力例1

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

出力例1

No

高橋君は、魚屋にたどり着くことができません。

入力例2

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

出力例2

Yes

入力例3

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

出力例3

No

入力例4

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

出力例4

Yes

入力例5

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

出力例5

No