CF1404E Bricks

一个砖块被定义为宽度为 $1$ 或高度为 $1$（或两者都是 $1$）的整数边长矩形。 现在有一个 $n\times m$ 的网格，每个格子被染成黑色或白色。一种铺砖方式是指在网格上放置砖块，使得每个黑色格子恰好被一个砖块覆盖，每个白色格子不被任何砖块覆盖。换句话说，砖块只能放在黑色格子上，且要覆盖所有黑色格子，任意两个砖块不能重叠。  上图是第一个测试用例的一种铺砖方式，共使用了 $5$ 块砖。实际上可以更优，只用 $4$ 块砖即可。请问，最少需要多少块砖才能完成有效铺砖？

第一行包含两个整数 $n$、$m$（$1\le n, m\le 200$），分别表示行数和列数。 接下来的 $n$ 行描述网格。第 $i$ 行包含一个长度为 $m$ 的字符串，第 $j$ 个字符表示第 $i$ 行第 $j$ 列格子的颜色。黑色格子用 "\#" 表示，白色格子用 "." 表示。 保证至少有一个黑色格子。

输出一个整数，表示完成有效铺砖所需的最少砖块数。

第一个测试用例可以用 $4$ 块竖直放置的砖块完成铺砖。 第三个测试用例可以用 $18$ 块砖块铺成如下图所示：  由 ChatGPT 4.1 翻译