[USACO05JAN] Muddy Fields G
题目描述
大雨侵袭了奶牛们的牧场。
牧场是一个 $R \times C$ 的矩形,其中 $1 \leq R,C \leq 50$。大雨将没有长草的土地弄得泥泞不堪,可是小心的奶牛们不想在吃草的时候弄脏她们的蹄子。为了防止她们的蹄子被弄脏,约翰决定在泥泞的牧场里放置一些木板。每一块木板的宽度为 $1$ 个单位,长度任意,每一个板必须放置在平行于牧场的泥地里。
约翰想使用最少的木板覆盖所有的泥地.一个木板可以重叠在另一个木板上,但是不能放在草地上。
输入输出格式
输入格式
第一行两个整数 $R,C$。
接下来 $R$ 行,每行 $C$ 个字符,描述牧场,其中 `*` 为泥地,`.` 为草地。
输出格式
输出一个整数,最少需要多少木板。
输入输出样例
输入样例 #1
4 4
*.*.
.***
***.
..*.
输出样例 #1
4