AT_arc005_3.[ARC005C] 器物損壊！高橋君

高桥君发现自己的卡已经过期了，于是他决定放弃，直接去鱼店买鳗鱼。
他所居住的城市呈长方形，被划分为网格状的区块。每个区块要么是道路，要么是围墙。高桥君只能在道路上沿东西南北方向移动，不能斜着走。同时，围墙区块是无法通过的。由于从他家到鱼店的路线非常复杂，仅靠步行很难到达。
不过，高桥君很有力气，他最多可以将与道路相邻的上下左右方向的围墙破坏 $2$ 次，将其变为道路。

请你判断高桥君是否能够到达鱼店。如果可以到达，输出 YES，否则输出 NO。输入格式如下，从标准输入读取。

$H$ $W$ $c_{(0,0)}c_{(0,1)}\ldots c_{(0,W-1)}$
$c_{(1,0)}c_{(1,1)}\ldots c_{(1,W-1)}$
$\vdots$
$c_{(H-1,0)}c_{(H-1,1)}\ldots c_{(H-1,W-1)}$

• 输入共 $H+1$ 行。
• 第 $1$ 行包含两个整数，分别表示城市南北方向的长度 $H(1\leq H\leq 500)$ 和东西方向的长度 $W(1\leq W\leq 500)$，以空格分隔。
• 从第 $2$ 行开始的 $H$ 行，每行包含该网格城市每个区块的状态 $c_{(i,j)}(0\leq i\leq H-1, 0\leq j\leq W-1)$。
• 第 $i$ 行第 $j$ 个字符 $c_{(i,j)}$ 为 s、g、.、# 之一，表示坐标 $(j,i)$ 的状态如下：
  • s：该区块为高桥君的家。
  • g：该区块为鱼店。
  • .：该区块为道路。
  • #：该区块为围墙。
• 高桥君可以通过家、鱼店、道路，但不能通过围墙。
• 不能走出给定城市的范围。
• s 和 g 各出现一次。

高桥君最多可以破坏 $2$ 次围墙，如果能从家到达鱼店，输出 YES，否则输出 NO。最后输出要换行。

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

YES

• 只要破坏 $(1,2)$、$(2,2)$、$(3,2)$ 中的任意一个围墙，就可以到达鱼店。

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

YES

• 没有围墙，可以直接到达。

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

YES

• 只需破坏 $(1,6)$、$(2,6)$ 这两个围墙即可到达。

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

YES

• 例如破坏 $(3,3)$、$(2,3)$ 这两个围墙即可到达。

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

NO

• 即使破坏 $2$ 个围墙，也无法到达鱼店。

第 $1$ 行包含两个整数 $H$ 和 $W$，以空格分隔。

接下来 $H$ 行，每行 $W$ 个字符，表示城市网格的状态。

如果能到达鱼店，输出 YES，否则输出 NO。最后输出换行。

无。

由 ChatGPT 4.1 翻译