AT_past202012_h コンベア

[problemUrl]: https://atcoder.jp/contests/past202012-open/tasks/past202012_h 縦 $ H $ マス、横 $ W $ マスの $ 2 $ 次元グリッドがあります。 上から $ i $ 行目、左から $ j $ 列目のマスをマス $ (i,\ j) $ と表すことにします。 マス $ (i,\ j) $ の情報が文字 $ s_{i,j} $ により与えられます。 $ s_{i,j} $ は `.` , `#` , `` , `v` のいずれかです。 `#` は入ることのできないマスであることを、 `` , `v` の $ 4 $ つは一方通行のマスであることを、 `.` は何もないマスであることを表します。 あなたは `#` でないマスを $ 1 $ つ選びロボットを置いたあと、以下の操作を繰り返してロボットをマス $ (r,\ c) $ まで動かします。 - 現在いるマスと上下左右に隣り合う、`#` でないマスに動かす。 このとき、グリッドの外に出てはいけない。 ただし、ロボットが一方通行のマスにいるときはその方向以外には動かすことができません。 より正確には、ロボットがマス $ (i,\ j) $ にいるとき、 - $ s_{i,j} $ が `` ならばマス $ (i,\ j\ +\ 1) $ 以外には動かすことができません。 - $ s_{i,j} $ が `v` ならばマス $ (i\ +\ 1,\ j) $ 以外には動かすことができません。 `#` でない各マスについて、そのマスにロボットを置いたときに、ロボットをマス $ (r,\ c) $ まで動かせるかを判定してください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ r $ $ c $ $ s_{1,1}\dots\ s_{1,W} $ $ \vdots $ $ s_{H,1}\dots\ s_{H,W} $

$ H $ 行にわたって、 $ W $ 文字の文字列を出力せよ。 $ i $ 行目の $ j $ 文字目には、 $ s_{i,j} $ が `#` である場合 `#` を、 $ s_{i,j} $ が `#` でない場合、ロボットをマス $ (i,j) $ からマス $ (r,\ c) $ まで動かせるならば `o` を、動かせないならば `x` を出力せよ。

### 注意 この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 1\ \le\ H,\ W $ - $ H\ \times\ W\ \le\ 10^6 $ - $ 1\ \le\ r\ \le\ H $ - $ 1\ \le\ c\ \le\ W $ - $ s_{i,j} $ は `.` , `#` , `` , `v` のいずれか - $ s_{r,c} $ は `#` でない ### Sample Explanation 1 ロボットをマス $ (3,3) $ に置いたとき、 $ (3,3)\ \rightarrow\ (2,3)\ \rightarrow\ (2,2)\ \rightarrow\ (1,2)\ \rightarrow\ (1,1) $ と動かすことでロボットをマス $ (1,1) $ まで移動させることができます。 ロボットをマス $ (3,1) $ に置くと、一方通行のマスがあるためロボットをマス $ (1,1) $ まで移動させることができません。