← 返回题目列表

AtCoder · arc005_3

C. 财产损失!高桥君

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

問題文

 仔细一看,卡已经过期了,于是他决定放弃,直接去鱼店买鳗鱼。
 他所居住的城市是长方形的,被分成网格状的部分。一个街区要么是一条路,要么是一堵墙,高桥可以沿着路向北、向南、向东或向西移动,但不能沿对角线移动。此外,您不能穿过围栏部分。从高桥家到鱼店的路很复杂,步行很难到达。
 不过,高桥对自己的体力很有信心,所以他站在两边面向马路的栅栏上。 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 以增量给出。

出力

栅栏 如果您从家到鱼店最多需要 2 次, 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 即使你摧毁它,你也无法到达鱼店。