Covering Holes in a Board

An N by M board has some holes. You want to cover all holes using tape of width 1.

You may treat the tape length as unlimited, but you want to minimize the number of tape pieces you cut. Each piece may be placed only horizontally or vertically. A piece must not cover any cell without a hole, but it may be placed over a hole cell that is already covered by another piece.

The first line contains N and M (1 <= N, M <= 50).

Each of the next N lines contains M adjacent characters describing the board. A cell without a hole is given as . and a cell with a hole is given as *.

Print the minimum possible number of tape pieces that must be cut.