레이팅 미적용For Mirko there is no greater happiness than finding a new roll of sticky tape, and
today he is especially happy because he had also found Slavko’s Advent calendar.
The Advent calendar can be represented as a table with \(n\) rows and \(m\) columns. Each
square contains a little window, and behind each window is a piece of chocolate. Slavko
had already opened some of the windows, and others are still closed.
Mirko decided to use his sticky tape to glue all closed windows shut. The tape is infinitely long, and
it is one calendar cell wide. Mirko can rip offa piece of tape and use it to glue some sequence of
horizontally or vertically adjacent closed windows shut. He doesn’t want to put more than one
piece of tape over some window, since he wants to remain friends with Slavko.
He is wondering what is the minimal number of pieces of tape he needs to glue all closed windows shut.
The first line contains integers \(n\) and \(m\) (\(1 \le n \le 1000\), \(1 \le m \le 10\)), dimensions of the Advent calendar.
Each of the following \(n\) lines contains \(m\) characters ’.’ and ’#’ that represent the Advent calendar. The
character ’.’ denotes an open window, and the character ’#’ denotes a closed window.
Output the minimal number of pieces of tape needed to glue all closed windows shut.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 35점 | Each closed window is adjacent to (shares a side with) at most two other closed windows. |
2 | 35점 | \(1 \le n \le 10\) |
3 | 40점 | No additional constraints. |
2 3
#.#
###34 3
.#.
###
.##
.#.34 4
####
#.#.
#.##
####5Clarification of the first example:
One possible solution is to use one piece of tape for the first column, one piece for the third column, and
one piece for the window in the second row and second column.