[ARC005C] 器物損壊!高橋君

题意翻译

给定一个 $H$ 行 $W$ 列的地图,它用 `s`,`g`,`#`,`.`四种字符表示。 `s` 表示起点。 `g` 表示终点。 `.` 表示空地。 `#` 表示障碍物。 现在高桥君站在起点,他每次可以向四个方向走一步,也可以跨越障碍物。如果存在从起点到终点的一种走法,使得他不跨越地图边界,并且跨越障碍物的次数不超过2次,输出 `YES`,否则输出 `NO`(输出的最后换一行)。

题目描述

[problemUrl]: https://atcoder.jp/contests/arc005/tasks/arc005_3 良く見てみるとカードの有効期限が切れていたので、高橋君は諦めて魚屋に直接うなぎを買いに行くことにしました。 彼の住む街は長方形の形をしており、格子状の区画に区切られています。区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。また、塀の区画は通ることができません。高橋君の家から魚屋までの道のりは非常に複雑なため、単純に歩くだけでは辿り着くことは困難です。 しかし、高橋君は腕力には自信があるので道に上下左右で面している塀を $ 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 $ 行で出力せよ。 なお、最後には改行を出力せよ。 ``` 4 5 s#### ....# ##### #...g ``` ``` YES ``` - $ (1,2), $ $ (2,2), $ $ (3,2) $ のいずれかの塀を壊すことで、魚屋に到達することができます。 ``` 4 4 ...s .... .... .g.. ``` ``` YES ``` - 塀が無いので到達することができます。 ``` 10 10 s......... #########. #.......#. #..####.#. ##....#.#. #####.#.#. g##.#.#.#. ###.#.#.#. ###.#.#.#. #.....#... ``` ``` YES ``` - $ (1,6), $ $ (2,6) $ の $ 2 $ つの塀を壊すことで到達することができます。 ``` 6 6 .....s ###... ###... ###### ...### g.#### ``` ``` YES ``` - 一例として $ (3,3) $, $ (2,3), $ の $ 2 $ つの塀を壊すと、到達することができます。 ``` 1 10 s..####..g ``` ``` NO ``` - 塀を $ 2 $ つ壊しても魚屋に到達することができません。

输入输出格式

输入格式


输出格式


输入输出样例

暂无测试点