离海最远的地方

Tags:

Description

有一个高H宽W的二维地图，地图中各点为陆地或是海洋，地图外均为海洋。

而其陆地的地形与各块地块与海洋之间的距离正相关。

这里，我们使用切比雪夫距离来作为衡量标准。

也即，可以简单的认为某块地块距离海洋的切比雪夫距离就是该地块的海拔。

于是，问题就来了，地图中海拔最高的地方的高度具体为多少？

切比雪夫距离[1]:
1、两点(x₁, y₁), (x₂, y₂)之间的切比雪夫距离 d=max(|x₁-x₂|, |y₁-y₂|)
2、对于任意一块陆地，其离海的切比雪夫距离为与各海洋块之间的切比雪夫距离中最小值

Input

第一行为H和W，分别表示地图的高和宽(1<=H,W<=3000)
接下来H行为表示地图的字符串
使用'#'表示陆地，'.'表示海洋

Output

输出最高的海拔

Samples

Hint

样例1：将绿色的部分看作陆地，蓝色的部分看作海洋，各个陆地块离海的切比雪夫距离如下图所示，显然，切比雪夫距离最大值为3。

样例2：岛中也可能存在内海，并且请注意地图范围外均为海洋。

Author

Source