C0595 红军的战略选择

红军的战略选择

题目描述

红军进入地势险峻的山区，侦察员将某片区域绘制成一张 H×W 的网格地图：

• 字符 '.'：代表山间小路或密林，可以通行。
• 字符 '#'：代表悬崖峭壁，部队无法通过。

红军可以从一个'.'格子移动到上、下、左、右相邻的'.'格子。为了迷惑敌人，指挥部需要寻找这片区域中距离最远的两个战略位置（起点和终点），使得即使走最短路径，所需的移动次数也是最多的。

请你计算出这个最大的移动次数，以评估这片战区的战略回旋纵深。

输入

第 1 行：2 个正整数 H 和 W，表示地图的行数和列数。

接下来 H行：每行 W 个字符（. 或 #），表示战区地形。

输出

1 个正整数，表示在这片战区中，两点间最短路径的最大值。

数据范围

1≤H,W≤20

地图至少包含两个"."，并且任意两个"."之间都可以通过若干次移动互相到达。

输入样例1

3 3

.#.

...

##.

输出样例1

4

输入样例2

3 5

...#.

.#.#.

.#...

输出样例2

10