← 返回题目列表

AtCoder · dfs_a

A. 深度优先搜索

中文机器翻译题面 查看原题

問題文

这个问题是用于讲座的问题。页面底部刊载了解说。

高桥君居住的街道呈长方形,并划分为网格状的区块。 长方形的各边分别朝东西和南北方向。 每个区块要么是道路,要么是围墙,高桥君可以沿东西南北方向移动,但不能斜着移动。 另外,围墙区块不能通行。

请数学上判断高桥君是否可以在不破坏围墙的情况下通过道路到达鱼店。


入力

输入将以以下形式从标准输入给出。

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}
  • 1 行表示街道的南北长度的整数 H(1≦H≦500) 和东西长度的整数 W(1≦W≦500) 通过空格分隔给出。
  • 2 从线 H 行表示网格状街道每个区块的状态 c_{i,j}(0≦i≦H-1, 0≦j≦W-1) 被给予。
    • i 行目 j 第x个字符是该区块的字符 c_{i,j} 分别是 代表第 s, g, ., # 中的任意一个所给,并表示坐标 (j,i) 处的状态如下。
      • s :表示该区域是房子。
      • g :表示该区域是鱼店。
      • . :表示该区域是道路。
      • # :表示该区域是围墙。
    • 高桥君可以通过房子、鱼店和道路,但不能通过围墙。
    • 不能通过给定街道的外部。
    • s 和 g 各自只能给出一个。

出力

围墙 1 在不破坏任何一堵围墙的情况下,从房子到鱼店可以到达的情况是 Yes无法到达的情况是 No 输出到标准输出 1 行。


入力例1

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

出力例1

No

高桥君无法到达鱼店。


入力例2

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

出力例2

Yes

入力例3

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

出力例3

No

入力例4

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

出力例4

Yes

入力例5

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

出力例5

No