← 返回题目列表

Codeforces · 1404/E

E. 砖块

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

砖块被定义为具有整数边长的矩形,其宽度为 $$$1$$$ 或高度为 $$$1$$$(或两者)。

有一个 $$$n\times m$$$ 网格,每个单元格的颜色为黑色或白色。平铺是一种将砖块放置到网格上的方法,使得每个黑色单元格都被一块砖块覆盖,并且每个白色单元格不被任何砖块覆盖。换句话说,砖块仅放置在黑色单元上,覆盖所有黑色单元,并且没有两块砖重叠。

使用 $$$5$$$ 砖块的第一个测试用例的平铺示例。仅使用 $$$4$$$ 砖块就可以做得更好。

制作有效瓷砖所需的最少砖块数量是多少?

输入

第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$1\le n, m\le 200$$$) — 分别是行数和列数。

接下来的 $$$n$$$ 行描述了网格。这些行的第 $$$i$$$ 包含长度为 $$$m$$$ 的字符串,其中第 $$$j$$$ 字符表示 $$$i$$$ 行、$$$j$$$ 列中单元格的颜色。黑色单元格由“#”给出,白色单元格由“.”给出。

保证至少有一个黑色单元格。

输出

输出一个整数,即所需的最小砖块数量。

示例

输入 #1

3 4
#.##
####
##..

输出 #1

4

输入 #2

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

输出 #2

6

输入 #3

10 8
####..##
#..#.##.
#..#.###
####.#.#
....####
.###.###
###.#..#
########
###..###
.##.###.

输出 #3

18

注意

第一个测试用例可以用垂直放置的 $$$4$$$ 砖块进行平铺。

第三个测试用例可以用 $$$18$$$ 砖块进行平铺,如下所示: