AT_abc151_d [ABC151D] Maze Master

[problemUrl]: https://atcoder.jp/contests/abc151/tasks/abc151_d 高橋君は、縦 $ H $ マス、横 $ W $ マスの $ H\ \times\ W $ マスからなる迷路を持っています。 上から $ i $ 行目、左から $ j $ 列目のマス $ (i,j) $ は、 $ S_{ij} $ が `#` のとき壁であり、`.` のとき道です。 道のマスからは、上下左右に隣接する道のマスに移動することができます。 迷路の外に移動すること、壁のマスへ移動すること、斜めに移動することはできません。 高橋君は、道のマスからスタートとゴールを自由に決め、迷路を青木君に渡します。 青木君は、移動回数が最小になるようにしてスタートからゴールまで移動します。 高橋君がスタートとゴールの位置を適切に定めたとき、青木君の移動回数は最大で何回になるでしょうか？

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ S_{11} $$ ... $$ S_{1W} $ $ : $ $ S_{H1} $$ ... $$ S_{HW} $

青木君の移動回数の最大値を出力せよ。

### 制約 - $ 1\ \leq\ H,W\ \leq\ 20 $ - $ S_{ij} $ は `.` か `#` - $ S $ は `.` を $ 2 $ つ以上含む - 任意の道のマスから任意の道のマスまで $ 0 $ 回以上の移動で到達できる ### Sample Explanation 1 高橋君が左上のマスをスタート、右下のマスをゴールにした場合、青木君の移動回数は $ 4 $ 回になります。 ### Sample Explanation 2 高橋君が左下のマスをスタート、右上のマスをゴールにした場合、青木君の移動回数は $ 10 $ 回になります。