2

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)}

• 入力は $H+1$ 行ある。
• $1$ 行目は、街の南北の長さとして整数 $H(1≦H≦500)$ と東西の長さとして整数 $W(1≦W≦500)$ が空白で区切られて与えられる。
• $2$ 行目からの $H$ 行には、格子状の街の各区画における状態 $c_{(i,j)}(0≦i≦H-1,$ $0≦j≦W-1)$ が与えられる。

2

YES

NO

1

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

YES

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

YES

• 塀が無いので到達することができます。

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

YES

• $(1,6),$ $(2,6)$ の $2$ つの塀を壊すことで到達することができます。

6 6
.....s
###...
###...
######
...###
g.####

YES

• 一例として $(3,3)$, $(2,3),$ の $2$ つの塀を壊すと、到達することができます。

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

NO

• 塀を $2$ つ壊しても魚屋に到達することができません。