#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
地图至少包含两个".",并且任意两个"."之间都可以通过若干次移动互相到达。