#XXSY26JBT4. 红军的战略选择

红军的战略选择

红军的战略选择

题目描述

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

字符 '.':代表山间小路或密林,可以通行。

字符 '#':代表悬崖峭壁,部队无法通过。

红军可以从一个'.'格子移动到上、下、左、右相邻的'.'格子。为了迷惑敌人,指挥部需要寻找这片区域中距离最远的两个战略位置(起点和终点),使得即使走最短路径,所需的移动次数也是最多的。请你计算出这个最大的移动次数,以评估这片战区的战略回旋纵深。

输入格式

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

接下来 H 行:每行 W 个字符(. 或 #),表示战区地形。

输出格式

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

输入输出样例

3 3
.#.
...
##.
4

3 3
...
...
...
4

说明提示

样例#1解释:选择左上角为起点,右下角为终点,需要移动4次。

样例#2解释:

​ 选择左上角为起点,右下角为终点,需要移动4次。

​ (1,1)到(2,2)的路径最长是8次移动,但是(1,1)到(2,2)最短只需走2步

​ (1,1)到(3,3)的路径最长是8次移动,但是(1,1)到(3,3)最短只需走4步

数据规模与约定

1≤H,W≤20

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