[USACO JAN05]泥泞的牧场

成绩 开启时间 2014年09月19日 星期五 10:08
折扣 0.8 折扣时间 2014年09月26日 星期五 10:08
允许迟交 是 关闭时间 2014年09月26日 星期五 10:08
输入文件 usaco_cover.in 输出文件 usaco_cover.out

【题目描述】

大雨侵袭了奶牛们的牧场。牧场是一个R*C的矩形，其中1<=R,C<=50。大雨将没有长草的土地弄得泥泞不堪，可是小心的奶牛们不想在吃草的时候弄脏她们的蹄子。

为了防止她们的蹄子被弄脏，约翰决定在泥泞的牧场里放置一些木板。每一块木板的宽度为1个单位，长度任意。每一个木板必须放置在平行于牧场边界的泥地里。

约翰想使用最少的木板覆盖所有的泥地。一个木板可以重叠在另一个木板上，但是不能放在草地上。

【输入格式】

第1行：两个整数R和C。

第2到R+1行：每行C个字符，其中“*”代表泥地，“.”代表草地。

【输出格式】

最少需要多少木板。

【样例输入】 

4 4
*.*.
.***
***.
..*.

【样例输出】 

4

【提示】

木板的放置方法如下：

1.2.

.333

444.

..2.

木板2和3，4重叠。

【来源】

USACO JAN05 Muddy Fields

Alex Schwendner,2004

译者蒋炎岩