D - 迷宫大师

分数：400分

问题描述

Takahashi拥有一个迷宫，它是一个由 $H \times W$ 个方块组成的网格，其中 $H$ 是水平行数，$W$ 是垂直列数。

如果第$i$行从上往下，第$j$列从左往右的方块是"墙"方块，那么$S_{ij}$等于#，如果是"道路"方块，那么$S_{ij}$等于.。

从一个道路方块，你可以移动到相邻的水平或垂直道路方块。

你不能移出迷宫，也不能移动到墙方块，也不能对角线移动。

Takahashi将选择一个起始方块和一个目标方块，它们可以是任何道路方块，并将迷宫交给Aoki。

然后，Aoki将从起始方块出发，走到目标方块，要求走的步数最少。

在这种情况下，求出Aoki最多需要走的步数。

约束条件

• $1 \leq H, W \leq 20$
• $S_{ij}$ 可以是 . 或者 #。
• $S$ 中至少出现两个 .。
• 任何道路方块都可以从任何道路方块经过零步或多步到达。

输入

输入是以以下格式从标准输入给出：

$H$ $W$

$S_{11}\ldots S_{1W}$

:

$S_{H1}\ldots S_{HW}$

输出

输出Aoki最多需要走的步数。

3 3
...
...
...

4

If Takahashi chooses the top-left square as the starting square and the bottom-right square as the goal square, Aoki has to make four moves.

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

10

If Takahashi chooses the bottom-left square as the starting square and the top-right square as the goal square, Aoki has to make ten moves.

样例解释

样例1：Takahashi选择左上方的方块作为起始方块，将右下方的方块作为目标方块，Aoki最多需要走4步。

样例2：Takahashi选择左下方的方块作为起始方块，将右上方的方块作为目标方块，Aoki最多需要走10步。