砖块被定义为具有整数边长的矩形,其宽度为 $$$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$$$ 砖块进行平铺,如下所示: