[USACO JAN05]泥泞的牧场

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file usaco_cover.in Output file 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

译者蒋炎岩