P6062 [USACO05JAN] Muddy Fields G

Heavy rain has hit the cows' pasture. The pasture is a rectangle of size $R \times C$, where $1 \leq R, C \leq 50$. The rain has turned the land without grass into muddy ground, but the careful cows do not want to dirty their hooves while grazing. To prevent their hooves from getting dirty, John decides to place some wooden boards on the muddy pasture. Each board has width $1$ unit and arbitrary length, and each board must be placed parallel to the rows or columns of the pasture on the muddy ground. John wants to use as few boards as possible to cover all muddy cells. One board may overlap another, but boards cannot be placed on grass.

The first line contains two integers $R, C$. The next $R$ lines each contain $C$ characters describing the pasture, where `*` represents mud and `.` represents grass.

Output one integer: the minimum number of boards needed.

Translated by ChatGPT 5