Covering Holes in a Board
Time limit2sMemory limit128 MB
Given a grid of holes, find the minimum number of horizontal or vertical tape strips (which may overlap on hole cells but never cover a non-hole cell) needed to cover every hole.
- Level
Medium7 of 10
- Topics
- Graph, Bit manipulation, Greedy, Matrix
- Solved
- No attempts yet
Problem
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.
Input
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 *.
Output
Print the minimum possible number of tape pieces that must be cut.