AT_abc351_d [ABC351D] Grid and Magnet

[problemUrl]: https://atcoder.jp/contests/abc351/tasks/abc351_d $ H $ 行 $ W $ 列のマス目があり、いくつか（$ 0 $ 個のこともある）のマスには磁石が置かれています。 マス目の状態は $ H $ 個の 長さ $ W $ の文字列 $ S_1,S_2,\ldots,S_H $ で表され、 $ S_i $ の $ j $ 文字目が `#` のとき上から $ i $ 行目かつ左から $ j $ 列目のマスには磁石が置かれていることを、 `.` のとき何も置かれていないことを表しています。 高橋君は鉄の鎧を着ており、あるマスにいるとき次のように移動することができます。 - 現在いるマスの上下左右に隣り合うマスのいずれかに磁石が置かれているとき、どこへも移動することができない。 - そうでないとき、上下左右に隣り合うマスのいずれかを選んでそのマスに移動することができる。 ただし、マス目の外に移動することはできない。 磁石が置かれていない各マスについて、そのマスの自由度を、「最初高橋くんがそのマスにいるとき、そこから移動を繰り返して到達できるマスの個数」として定義します。 マス目のうち磁石が置かれていないマスの中における、マスの自由度の最大値を求めてください。 ただし、自由度の定義において、「移動を繰り返して到達できるマス」とは、最初にいるマスからそのマスまで移動を繰り返して到達する方法（$ 1 $ 回も移動しないものも含む）が $ 1 $ つ以上存在するようなマスのことであり、 最初のマスから始めてすべてのそのようなマスを巡るような移動方法が存在する必要はありません。特に（磁石の置かれていない）各マス自身は、そのマスから「移動を繰り返して到達できるマス」につねに含まれることに注意してください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_H $

マス目のうち磁石が置かれていないマスの中における、マスの自由度の最大値を出力せよ。

### 制約 - $ 1\leq\ H,W\leq\ 1000 $ - $ H,W $ は整数 - $ S_i $ は `.` と `#` のみからなる長さ $ W $ の文字列 - 磁石の置かれていないマスが少なくとも $ 1 $ つ存在する。 ### Sample Explanation 1 上から $ i $ 行目かつ左から $ j $ 列目のマスを $ (i,j) $ で表します。 高橋君が最初に $ (2,3) $ にいるとき、高橋君の移動の例としては次のようなものなどが考えられます。 - $ (2,3)\to\ (2,4)\to\ (1,4)\to\ (1,5)\to\ (2,5) $ - $ (2,3)\to\ (2,4)\to\ (3,4) $ - $ (2,3)\to\ (2,2) $ - $ (2,3)\to\ (1,3) $ - $ (2,3)\to\ (3,3) $ よって、途中で到達しているマスも含めて高橋君は $ (2,3) $ から少なくとも $ 9 $ 個のマスに到達することができます。 一方、これら以外のマスには到達することができないため、$ (2,3) $ の自由度は $ 9 $ となります。 これは磁石が置かれていない各マスの自由度のうち最大であるため、$ 9 $ を出力します。 ### Sample Explanation 2 磁石が置かれていないどのマスについても、上下左右に隣り合うマスのいずれかに磁石が置かれています。 よって、磁石が置かれていないどのマスからも移動することはできず、マスの自由度は $ 1 $ となります。 そのため、$ 1 $ を出力します。