迷宫大师

题目描述

高桥君有一个由竖 $H$ 格、横 $W$ 格组成的 $H \times W$ 格的迷宫。

从上数第 $i$ 行、从左数第 $j$ 列的格子 $(i,j)$,当 $S_{ij}$ 为 # 时是墙壁,为 . 时是道路。

从道路的格子可以移动到上下左右相邻的道路格子。

不能移动到迷宫外、不能移动到墙壁格子、不能斜向移动。

高桥君在道路的格子上自由决定起点和终点,然后把迷宫交给青木君。

青木君会以移动次数最少的方式从起点移动到终点。

当高桥君合适地选定起点和终点的位置时,青木君的移动次数最大是多少?

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出青木君移动次数的最大值。

样例

3 3
...
...
...

4

如果高桥君把左上角的格子设为起点、右下角的格子设为终点,则青木君的移动次数为 $4$。

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

10

如果高桥君把左下角的格子设为起点、右上角的格子设为终点,则青木君的移动次数为 $10$。

数据范围

• $1 \leq H,W \leq 20$
• $S_{ij}$ 是 . 或 #
• $S$ 至少包含 $2$ 个 .
• 从任意道路格子都可以通过 $0$ 次以上的移动到达任意道路格子