← 返回题目
题库练习 [ABC151D] Maze Master
← 上一题 下一题 →

A7526 | [ABC151D] Maze Master

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

高桥君有一个由 $H$ 行 $W$ 列组成的 $H \times W$ 格子的迷宫。

第 $i$ 行第 $j$ 列的格子 $(i,j)$，当 $S_{ij}$ 为 # 时表示墙壁，为 . 时表示道路。

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

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

高桥君可以自由选择一个道路格子作为起点和终点，然后把迷宫交给青木君。

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

请问，高桥君如何选择起点和终点，使得青木君的最小移动次数最大？输出这个最大值。

输入格式

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

> $H$ $W$
> $S_{11} \ldots S_{1W}$
> $\vdots$
> $S_{H1} \ldots S_{HW}$

输出格式

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

输入输出样例

输入 #1
3 3
...
...
...
输出 #1
4
输入 #2
3 5
...#.
.#.#.
.#...
输出 #2
10
C++ 编辑器
输入
输出