AtCoder Regular Contest 005

C - 器物損壊!高橋君


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 64MB

問題文

 良く見てみるとカードの有効期限が切れていたので、高橋君は諦めて魚屋に直接うなぎを買いに行くことにしました。
 彼の住む街は長方形の形をしており、格子状の区画に区切られています。区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。また、塀の区画は通ることができません。高橋君の家から魚屋までの道のりは非常に複雑なため、単純に歩くだけでは辿り着くことは困難です。
 しかし、高橋君は腕力には自信があるので道に上下左右で面している塀を 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 : その区画が魚屋であることを表す。
      • . : その区画が道であることを表す。
      • # : その区画が塀であることを表す。
    • 高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。
    • 与えられた街の外を通ることはできない。
    • sg はそれぞれ 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 つ壊しても魚屋に到達することができません。

Source name

ARC 005

Submit提出する