P7171 [COCI 2020/2021 #3] Selotejp

In Mirko’s opinion, nothing is happier than finding a brand-new roll of tape, and today he is especially happy because he found Slavko’s Advent calendar.

An Advent calendar can be represented as a grid with $n$ rows and $m$ columns. Each cell contains a small window, and behind each window there is a piece of chocolate. Slavko has already opened some windows, while the others are still closed. Mirko decides to use his tape to seal all closed windows. The tape has unlimited length, and its width fits exactly one window. Mirko can tear off a piece of tape to seal **a consecutive segment of closed windows in one horizontal row or one vertical column**. He does not want to put more than one piece of tape on any window, because he still wants to remain Slavko’s friend. He wants to know the **minimum** number of tape pieces needed to seal **all** closed windows.

The first line contains two integers $n, m$, which describe the size of the Advent calendar. The next $n$ lines each contain $m$ characters, describing the cells of the calendar. `.` means an opened window, and `#` means a closed window.

Output the minimum number of tape pieces needed to seal all closed windows.

**[Sample Explanation #1]** One valid solution is to use tape on the entire first column, the entire third column, and the cell at row $2$, column $2$. **[Constraints]** | Subtask | Points | Constraints and notes | | :----------: | :----------: | :----------: | | $1$ | $35$ | Each window is adjacent to at most two closed windows | | $2$ | $35$ | $1 \le n \le 10$ | | $3$ | $40$ | None | For $100\%$ of the testdata, $1 \le n \le 1000$, $1 \le m \le 10$. **[Notes]** **The scoring of this problem follows the original COCI problem, with a maximum of $110$ points.** **Translated from [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf) _T4 Selotejp_.** Translated by ChatGPT 5