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 翻译