配点 : $400$ 点

問題文

高橋君は、縦 $H$ マス、横 $W$ マスの $H \times W$ マスからなる迷路を持っています。

上から $i$ 行目、左から $j$ 列目のマス $(i,j)$ は、 $S_{ij}$ が # のとき壁であり、. のとき道です。

道のマスからは、上下左右に隣接する道のマスに移動することができます。

迷路の外に移動すること、壁のマスへ移動すること、斜めに移動することはできません。

高橋君は、道のマスからスタートとゴールを自由に決め、迷路を青木君に渡します。

青木君は、移動回数が最小になるようにしてスタートからゴールまで移動します。

高橋君がスタートとゴールの位置を適切に定めたとき、青木君の移動回数は最大で何回になるでしょうか？

制約

• $1 \leq H,W \leq 20$
• $S_{ij}$ は . か #
• $S$ は . を $2$ つ以上含む
• 任意の道のマスから任意の道のマスまで $0$ 回以上の移動で到達できる

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$

$S_{11}$$...$$S_{1W}$

$:$

$S_{H1}$$...$$S_{HW}$

出力

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

3 3
...
...
...

4

高橋君が左上のマスをスタート、右下のマスをゴールにした場合、青木君の移動回数は $4$ 回になります。

3 5
...#.
.#.#.
.#...

10

高橋君が左下のマスをスタート、右上のマスをゴールにした場合、青木君の移動回数は $10$ 回になります。