问题描述

当高桥君注意到他的信用卡已经过期时，他决定放弃在网上购买鳗鱼，直接去鱼店购买。他所住的城市是一个长方形，并被划分为网格状的区域。每个区域要么是道路，要么是围墙，高桥君只能在道路上进行东西南北的移动，不能斜向移动。此外，他不能穿过围墙。由于高桥君家到鱼店的路线非常复杂，简单地步行是很困难的。然而，由于高桥君很有力气，他可以打破道路两边的围墙最多两次，将其变成道路。

请判断高桥君是否可以到达鱼店。

---

输入

输入被标准格式输入流给出。$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$ 行。

• 第一行包含两个整数 $H~(1≦H≦500)$ 和 $W~(1≦W≦500)$，分别表示城市的南北长度和东西长度。

• 第二行到第 $H+1$ 行依次给出了每个网格区域的状态 $c_{(i,j)}~(0≦i≦H-1,~0≦j≦W-1)$。

• 第 $i$ 行第 $j$ 个字符 $c_{(i,j)}$ 是 s, g, ., # 中的一个，它表示坐标 $(j,i)$ 的状态。

• s : 表示该区域是高桥君的家。

• g : 表示该区域是鱼店。

• . : 表示该区域是道路。

• # : 表示该区域是围墙。

• 高桥君可以通过家、鱼店和道路，但不能通过围墙。

• 不能走出给定的城市范围。

• 给定的输入中只会有一个 s 和一个 g。

输出

如果高桥君可以通过打破最多两次围墙，从家到达鱼店，则输出 YES；否则输出 NO。输出应在标准输出上占一行。最后要输出一个换行符。

---

示例 1

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

输出 1

YES

可以打破 $(1,2),$ $(2,2),$ $(3,2)$ 位置的围墙之一，就可以到达鱼店。

---

示例 2

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

输出 2

YES

没有围墙，可以到达鱼店。

---

示例 3

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

输出 3

YES

可以打破 $(1,6),$ $(2,6)$ 位置的两面围墙，就可以到达鱼店。

---

示例 4

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

输出 4

YES

可以打破 $(3,3)$ 和 $(2,3)$ 位置的两面围墙，就可以到达鱼店。

---

示例 5

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

输出 5

NO

无论打破两面围墙，都无法到达鱼店。

---

来源

ARC 005