AT_past202012_k 的あて

[problemUrl]: https://atcoder.jp/contests/past202012-open/tasks/past202012_k あなたは $ 4\ \times\ 4 $ のグリッドを使って的あてゲームをしています。 グリッドの上から $ i $ 行目、左から $ j $ 列目のマスには、$ S_{i,j} $ が `.` のとき的はなく、`#` のとき的があります。全ての的に $ 1 $ 度以上ボールを当てるとゲームクリアです。 あなたがあるマスを狙ってボールを投げると、狙ったマスか $ 1 $ マス分上下左右にズレた場所(グリッド外も含む)にそれぞれ $ \dfrac{1}{5} $ の確率で飛んでいき、そこに的があれば当たります。 ゲームの進行に伴い狙うマスを適切に選択するとき、ゲームをクリアするまでにボールを投げる回数の期待値は最小でいくらになりますか？

入力は以下の形式で標準入力から与えられる。 > $ S_{1,1}S_{1,2}S_{1,3}S_{1,4} $ $ S_{2,1}S_{2,2}S_{2,3}S_{2,4} $ $ S_{3,1}S_{3,2}S_{3,3}S_{3,4} $ $ S_{4,1}S_{4,2}S_{4,3}S_{4,4} $

ボールを投げる回数の期待値の最小値を出力せよ。 正しい値との絶対誤差または相対誤差が $ 10^{-6} $ 以下であれば正解とみなされる。

### 注意 この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ S_{i,j} $ は `.` または `#` - $ S_{i,j} $ のうち少なくとも $ 1 $ 個は `#` である ### Sample Explanation 1 的にボールが当たるまでの回数の期待値は $ 5 $ です。グリッドの外へボールが飛んでいくこともあります。 ### Sample Explanation 2 $ 2 $ つある的のどちらかにボールが当たるまでは、上の的を狙います。一方の的に当たったあとは、残りの的を狙います。 ### Sample Explanation 3 最初のうちは $ 4 $ つの的の中央にある、的のないマスを狙うのが最適です。