#1029. 霍霍想回家

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: new_user_4

题目描述

众所周知,藿藿,是一位可怜又弱小的狐人小姑娘,也是怕鬼捉鬼的罗浮十王司见习判官。

名为“尾巴”的岁阳被十王司的判官封印在她的尾巴上,也成了她不可或缺的伙伴。

一天,藿藿由于害怕,想从十王司早点下班回家,但尾巴并不满意,他想延长藿藿的上班时间,他要求藿藿在绥园迷宫里,走出最大的移动次数,而藿藿想要快点下班,每次都会以最小移动次数的方式从起点移动到终点,作为开拓者,你能帮帮她吗?

总的来说,绥园是一个由 n 行 m 列组成的迷宫S,迷宫中的每个单元格 (i,j),如果#,表示墙,如果. ,表示道路。你可以从一个有道路的单元格移动到上下左右相邻的有道路的单元格。你不能走出迷宫、走到墙上的单元格,也不能进行斜对角移动。尾巴可以自由选择道路上的起点和终点,然后将迷宫交给藿藿。藿藿将以最小移动次数的方式从起点移动到终点。当尾巴选择适当的起点和终点时,藿藿的最大移动次数是多少?

piDdrkQ.png

输入格式

第一行输入两个整型变量 n 、 m 接下来 n 行 m 列输入迷宫。

输出格式

输出藿藿移动次数的最大值

样例

样例输入 #1

3 3
...
...
...

样例输出 #1

4

样例输入 #2

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

样例输出 #2

10

数据范围与提示

S 中至少有两个 .(空地)

你可以在零次或更多次移动中从任意有道路的单元格到达另一个有道路的单元格。