問題文
他所居住的城市是长方形的,被分成网格状的部分。一个街区要么是一条路,要么是一堵墙,高桥可以沿着路向北、向南、向东或向西移动,但不能沿对角线移动。此外,您不能穿过围栏部分。从高桥家到鱼店的路很复杂,步行很难到达。
不过,高桥对自己的体力很有信心,所以他站在两边面向马路的栅栏上。 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) 。 来自行
- i 行目 j 字符数 c_{(i,j)} 分别是
s,g,.,#由坐标之一给出 (j,i) 表示以下状态。 s:表示该地块是房屋。g:表示该区域是鱼店。.:表示该路段是道路。#:表示该部分是栅栏。- 高桥可以穿过房屋、鱼店和道路,但不能穿过墙壁。
- 无法通过给定城市之外。
s和 将其放在g分别是 1 以增量给出。
出力
YES,如果找不到, NO 到标准输出 1 行输出。请在末尾输出换行符。
入力例 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) 的 2 摧毁两堵墙即可到达。
入力例 4
6 6 .....s ###... ###... ###### ...### g.####
出力例 4
YES
- 举个例子 (3,3), (2,3), 的 2 你可以通过摧毁两堵墙来到达它。
入力例 5
1 10 s..####..g
出力例 5
NO
- 栅栏 如果您从家到鱼店最多需要 2 即使你摧毁它,你也无法到达鱼店。