← 返回题目列表

AtCoder · abc151_d

D. 迷宫大师

中文机器翻译题面 查看原题

分数: 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

如果高桥选择左下方格作为起始方格,选择右上角方格作为目标方格,青木必须走十步。