Maze Master

题目描述

Takahashi 有一个迷宫，这是一个 $H \times W$ 的方格，包含 $H$ 行和 $W$ 列。 位于自上而下第 $i$ 行、第 $j$ 列的方格如果 $S_{ij}$ 是 # 则为“墙”方格，如果 $S_{ij}$ 是 $.$ 则为“通路”方格。 从一个通路方格可以移动到水平方向或垂直方向相邻的通路方格。 你不能移出迷宫、移动到墙方格，或斜向移动。 Takahashi 将选择一个起始方格和一个目标方格，这两个都可以是任意的通路方格，然后把迷宫给 Aoki。 Aoki 然后会以所需的最小移动次数从起始方格走到目标方格。 在这种情况下，求 Aoki 最多需要移动的步数。

输入格式

输入从标准输入给出，格式如下： $H$ $W$ $S_{11}$$...$$S_{1W}$ : $S_{H1}$$...$$S_{HW}$

输出格式

输出 Aoki 最多需要移动的步数。

3 3
...
...
...

4

3 5
...#.
.#.#.
.#...

10

提示

$1 \leq H,W \leq 20$ $S_{ij}$ 是 $.$ 或 #。 $S$ 至少包含两个 $.$。 任意通路方格都可以通过零次或多次移动到达任意其他通路方格。如果 Takahashi 选择左上角方格作为起始方格、右下角方格作为目标方格，Aoki 需要移动四步。
如果 Takahashi 选择左下角方格作为起始方格、右上角方格作为目标方格，Aoki 需要移动十步。

标签: AtCoder|abc151D

来源

AtCoder|abc151D