Problem1127--最小覆盖2(模型转换:草场淹水)

1127: 最小覆盖2(模型转换:草场淹水)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Status] [Submit] [Creator:]

Description

【题目描述】
一个R行C列的矩形草场(1≤ R ≤50,1≤ C ≤50)。 
某些地方淹水了。 
现在需要铺垫一些木板覆盖全部被淹的草地。
木板宽为1,长度不限。 
每块木板摆放必须对齐平行于两侧边界。
木板可以互相重叠,但不能盖住没有被水淹的草地。
求最少的木板数目。
【输入】
第1行:两个用空格隔开的整数:R和C。
第2至第R +1行:每行包含一行字符串,“*”代表被淹水的草地,“.” 代表没被水淹的草地。没有多余空格存在。 
【输出】

输出一行,一个整数,表示最小的木板数目。 

Sample Input
4 4
*.*.
.***
***.
..*.
Sample Output
4


Source/Category