C - 器物損壊！高橋君
Editorial
/ 
良く見てみるとカードの有効期限が切れていたので、高橋君は諦めて魚屋に直接うなぎを買いに行くことにしました。
彼の住む街は長方形の形をしており、格子状の区画に区切られています。区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。また、塀の区画は通ることができません。高橋君の家から魚屋までの道のりは非常に複雑なため、単純に歩くだけでは辿り着くことは困難です。
しかし、高橋君は腕力には自信があるので道に上下左右で面している塀を 2 回までなら壊して道にすることができます。
高橋君が魚屋に辿り着くことができるかどうか答えてください。
入力は以下の形式で標準入力から与えられる。
塀を 2 回まで越えることで、家から魚屋まで辿り着くことができる場合は
なお、最後には改行を出力せよ。
/ 
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
彼の住む街は長方形の形をしており、格子状の区画に区切られています。区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。また、塀の区画は通ることができません。高橋君の家から魚屋までの道のりは非常に複雑なため、単純に歩くだけでは辿り着くことは困難です。
しかし、高橋君は腕力には自信があるので道に上下左右で面している塀を 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 つ壊しても魚屋に到達することができません。