Problem Description

This problem is for educational purposes. The explanation is posted at the bottom of the page.

Takahashi's town is rectangular and divided into grid sections. Each side of the rectangle is parallel to the east-west or north-south direction. Each section is either a road or a wall, and Takahashi can move east, west, north, or south on roads but not diagonally. He cannot pass through walls.

Determine if Takahashi can reach the fish shop by traveling only on roads without breaking any walls.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains two integers $ H(1≦H≦500) $ and $ W(1≦W≦500) $ separated by a space, representing the length of the town in the north-south direction and the east-west direction, respectively.
• The next $ H $ lines contain the state $c_{i,j}(0≦i≦H-1,\ 0≦j≦W-1)$ of each grid section in the town.
• The $ i $-th line $ j $-th character $ c_{i,j} $ is given as one of s, g, ., #, representing the state of the coordinate $ (j,i) $ as follows:
  • s: The section is a house.
  • g: The section is a fish shop.
  • .: The section is a road.
  • #: The section is a wall.
• Takahashi can pass through houses, fish shops, and roads, but not walls.
• He cannot go outside the given town.
• There is exactly one s and one g in the input.

Output Format

Output Yes to the standard output if Takahashi can reach the fish shop without breaking any walls, otherwise output No.

Sample Input and Output

Sample Input #1

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

Sample Output #1

No

Sample Input #2

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

Sample Output #2

Yes

Sample Input #3

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

Sample Output #3

No

Sample Input #4

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

Sample Output #4

Yes

Sample Input #5

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

Sample Output #5

No

Notes/Hints

Explanation

Depth-First Search Flood Fill from AtCoder Inc.

Sample Explanation 1

Takahashi cannot reach the fish shop.

见题面 Input 部分

见题面 Output 部分