题目描述

给定一个有 $H$ 行 $W$ 列的黑白格子。格子的状态由 $A_{11}$ 到 $A_{HW}$ 共 $HW$ 个字符表示，从上到下第 $i$ 行，从左到右第 $j$ 列的格子如果是黑色，则 $A_{ij}$ 为 #，如果是白色，则 $A_{ij}$ 为 .。

你可以重复进行如下操作，直到所有格子都变为黑色：

• 所有与至少一个黑色格子在边上相邻的白色格子会同时变为黑色。

请你求出需要进行多少次操作才能使所有格子都变为黑色。保证初始格子中至少有一个黑色格子。

输入格式

输入以如下格式从标准输入给出。

$H$ $W$
$A_{11}A_{12}\ldots A_{1W}$
$A_{21}A_{22}\ldots A_{2W}$
$\vdots$
$A_{H1}A_{H2}\ldots A_{HW}$

输出格式

输出需要进行的操作次数。

样例 1

输入

3 3
...
.#.
...

输出

2

样例 2

输入

6 6
..#..#
......
#..#..
......
.#....
....#.

输出

3

说明/提示

限制条件

• $1 \leq H, W \leq 1000$
• $A_{ij}$ 只会是 # 或 .
• 输入的格子中至少有一个黑色格子。

样例解释 1

第一次操作后，除了四个角以外的格子都会变成黑色，再进行一次操作后，所有格子都变为黑色。

由 ChatGPT 4.1 翻译