分数: 400 点
问题陈述
高桥有一个迷宫,它是一个网格 H \times W 方块与 H 水平行和 W 垂直列。
广场 i从顶部开始的第行和 j- 第列是一个“墙”方块,如果 S_{ij} is #,和一个“道路”方块,如果 S_{ij} is ..
从道路方块,您可以移动到水平或垂直相邻的道路方块。
你无法移出迷宫、移至墙方格或沿对角线移动。
高桥会选择一个起始方格和一个目标方格,可以是任何道路方格,并将迷宫交给青木。
青木随后将以所需的最少步数从起始方格移动到目标方格。
在这种情况下,找出 Aoki 必须进行的最大可能移动次数。
约束
- 1 \leq H,W \leq 20
- S_{ij} is
.or#. - S 至少出现两次
.. - 任何道路方块可以通过零次或多次移动从任何道路方块到达。
输入
输入由标准输入按以下格式给出:
H W
S_{11}...S_{1W}
:
S_{H1}...S_{HW}
输出
打印 Aoki 必须进行的最大可能移动次数。
示例输入 1
3 3 ... ... ...
示例输出 1
4
如果高桥选择左上角的方块作为起始方块,右下角的方块作为目标方块,青木必须走四步。
示例输入 2
3 5 ...#. .#.#. .#...
示例输出 2
10
如果高桥选择左下方格作为起始方格,选择右上角方格作为目标方格,青木必须走十步。