[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 $ つ壊しても魚屋に到達することができません。