20220206 - 最远点之间的最近距离

在一个hw列的矩阵中,#表示无法到达,.表示可以到达,移动时可以向上下左右移动,但不能移动到#的格子也不能移动到矩阵外。输出从所需移动次数最多的两个.之一移动到另一个需要的最少步数。

输入

第一行,两个正整数h,w,分别表示行数和列数。

接下来h行,每行w个字符,每个字符均为#或.,表示该位置能否到达。

对于100%的数据:

1 \le w,h \le 20

数据保证至少有两个可以互相到达的#

输出

一行,一个整数。

样例

输入

3 3
...
...
...

输出

4

输入

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

输出

10
时间限制 1000 毫秒
内存限制 128 MB
统计
上一题 下一题