AT_maximum_cup_2018_b 駆け抜けろ!埼大山車部!!
Description
[problemUrl]: https://atcoder.jp/contests/maximum-cup-2018/tasks/maximum_cup_2018_b
サイタマでは年に一度の山車のお披露目会がある。もっとも美しい山車には賞金が出ると聞いた埼大くんと埼大くんの友達はお披露目会に参加することにした。
お披露目会の会場に向かう途中、隣街の男衆が山車に乗って邪魔をしてきた。男衆が山車の右側に$ a $人、左側に$ b $人乗っているようだ。
どうしても賞金が欲しい埼大くんたちは完璧な山車を披露したいため、会場に到着するまでに男衆を全員振り払う必要がある。
単位時間内にとりうる山車の動きは次の3パターンである。
1. 左に$ 90 $度向きを変えてから一マス前進する。
2. 右に$ 90 $度向きを変えてから一マス前進する。
3. 向きを変えずに一マス前進する。
1.の動きにより右側に乗っている人を、2.の動きにより左側に乗っている人を、一人づつ振り落とすことができる。
しかし必要以上に向きを変えたくないため、1.の動きを$ a $回行った以後は1.の、2.の動きを$ b $回行った以後は2.の動きを行わない。
埼大くんたちは地図を見てルートを決めることにした。
地図の縦の長さは $ h $ 、横の長さは $ w $ で、通れる場所は $ '.' $ 、通れない場所は $ '#' $ である。通過する街はマス目状に区切られており、地図上では $ i $行$ j $ 列目のマス は $ c(i,j) $ で表される。
現在地は $ c(2,2) $ 、会場は $ c(h-1,w-1) $ である。現在地と、会場は $ '.' $ であることが保証されている。
地図の一番外側はすべて $ '#' $ で囲まれている。 $ c(1,1)~c(1,w) $ に面している方面の方角が北であり、埼大くんたちは最初南を向いている。
埼大くんたちは無事にお披露目会に参加できるかどうかを判定せよ。
Input Format
入力は以下の形式で標準入力から与えられる。
> $ a $ $ b $ $ h $ $ w $ $ c(1,1)c(1,2)\ …\ c(1,w) $ $ c(2,1)c(2,2)\ …\ c(2,w) $ $ : $ $ c(h,1)c(h,2)\ …\ c(h,w) $
1行目に右側に乗ってきた男衆の人数$ a $、左側に乗ってきた男衆の人数$ b $が与えられる。 2行目に地図の縦の長さ$ h $、横の長さ$ w $が与えられる。 続く$ h $行に長さ$ w $の文字列が$ 1 $行ずつ与えられる。 各文字$ c(i,j) $は$ '.' $もしくは$ '#' $のいずれかであり、$ '.' $は通れる地点であり、$ '#' $は通れない地点であることを表す。
Output Format
埼大くんたちが無事にお披露目会に参加できるなら Yes 、できないなら No を出力せよ。
Explanation/Hint
### 制約
- $ 1\ \leq\ a,\ b\ \leq\ 15 $
- $ 3\ \leq\ h,\ w\ \leq\ 15 $