题目描述

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

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

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

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

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

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

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

输入格式

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

$H$ $W$ $S_{11}$$...$$S_{1W}$ $:$ $S_{H1}$$...$$S_{HW}$

输出格式

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

题目大意

• 给出一个H行W列的方格，字符是'#'则表示墙，'.'表示空地。可从一个空地走到上下左右的空地，但不能对角线走。空地可以互相到达。
• 问：距离最大的两个空地之间的距离。
• 1≤H,W≤20

3 3
...
...
...

4

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

10

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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