← 返回题目列表

AtCoder · agc033_a

A. 越来越黑

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给你一个正方形网格,其中 H 水平行和 W 垂直列,其中每个方块都漆成白色或黑色。 HW 字符来自 A_{11} to A_{HW} 代表方块的颜色。 A_{ij} is # 如果正方形位于 i从顶部开始的第行和 j从左边算起的第列是黑色的,并且 A_{ij} is . 如果该方块是白色的。

我们将重复执行以下操作,直到所有方块都变成黑色:

  • 每个与黑色方块共享一条边的白色方块都会变成黑色。

查找将执行的操作数。 初始网格至少有一个黑色方块。

约束

  • 1 \leq H,W \leq 1000
  • A_{ij} is # or ..
  • 给定的网格至少有一个黑色方块。

输入

输入由标准输入按以下格式给出:

H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}

输出

打印将执行的操作数。


示例输入 1

3 3
...
.#.
...

示例输出 1

2

一次操作后,网格中除角之外的所有区域都会变黑。再进行一次操作后,所有的方块都会变成黑色。


示例输入 2

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

示例输出 2

3