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.

Subtask 1 (35 points): Each closed window is adjacent to (shares a side with) at most two other closed windows.

Subtask 2 (35 points): \(1 \le n \le 10\)

Subtask 3 (40 points): No additional constraints.

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.

생성자가 기록되지 않았습니다.

출처 COCI 2020/2021 Contest 3