A7526. [ABC151D] Maze Master
编程题
普及-
知识点
题目描述
高桥君有一个由 $H$ 行 $W$ 列组成的 $H \times W$ 格子的迷宫。
第 $i$ 行第 $j$ 列的格子 $(i,j)$，当 $S_{ij}$ 为
从道路格子可以移动到上下左右相邻的道路格子。
不能移动到迷宫外部、墙壁格子，也不能斜向移动。
高桥君可以自由选择一个道路格子作为起点和终点，然后把迷宫交给青木君。
青木君会以最少的移动次数从起点移动到终点。
请问，高桥君如何选择起点和终点，使得青木君的最小移动次数最大？输出这个最大值。
第 $i$ 行第 $j$ 列的格子 $(i,j)$，当 $S_{ij}$ 为
# 时表示墙壁，为 . 时表示道路。从道路格子可以移动到上下左右相邻的道路格子。
不能移动到迷宫外部、墙壁格子，也不能斜向移动。
高桥君可以自由选择一个道路格子作为起点和终点，然后把迷宫交给青木君。
青木君会以最少的移动次数从起点移动到终点。
请问，高桥君如何选择起点和终点，使得青木君的最小移动次数最大？输出这个最大值。
输入格式
输入从标准输入按以下格式给出。
> $H$ $W$
> $S_{11} \ldots S_{1W}$
> $\vdots$
> $S_{H1} \ldots S_{HW}$
> $H$ $W$
> $S_{11} \ldots S_{1W}$
> $\vdots$
> $S_{H1} \ldots S_{HW}$
输出格式
输出青木君的最小移动次数的最大值。
输入输出样例
输入 #1
3 3 ... ... ...
输出 #1
4
输入 #2
3 5 ...#. .#.#. .#...
输出 #2
10
说明/提示
## 限制条件
- $1 \leq H, W \leq 20$
- $S_{ij}$ 只包含
- $S$ 至少包含两个
- 任意两个道路格子之间都可以通过 $0$ 次或多次移动到达
## 样例解释 1
如果高桥君选择左上角格子为起点，右下角格子为终点，青木君的移动次数为 $4$。
## 样例解释 2
如果高桥君选择左下角格子为起点，右上角格子为终点，青木君的移动次数为 $10$。
- $1 \leq H, W \leq 20$
- $S_{ij}$ 只包含
. 或 #- $S$ 至少包含两个
.（即至少有两个道路格子）- 任意两个道路格子之间都可以通过 $0$ 次或多次移动到达
## 样例解释 1
如果高桥君选择左上角格子为起点，右下角格子为终点，青木君的移动次数为 $4$。
## 样例解释 2
如果高桥君选择左下角格子为起点，右上角格子为终点，青木君的移动次数为 $10$。