P7171 [COCI 2020/2021 #3] Selotejp

在 Mirko 看来，没有比找到一卷新的胶带纸要更令人快乐，而今天他格外开心，因为他找到 Slavko 的基督日历。

基督日历可以被一个 $n$ 行 $m$ 列的表格所表示。每个方格包含一个小窗口，而每个小窗口后有一块巧克力。Slavko 已经打开了部分窗口，而其他的处于关闭状态。 Mirko 决定用他的胶带把所有关闭的窗户都粘住。胶带纸长度无限大，并且宽度与一个窗口吻合。Mirko 可以撕下一部分胶带纸来将**一横排或一纵列连续的关闭的窗口**粘上。他不想在某个窗户上贴超过一条胶带，因为他仍旧想做 Slavko 的朋友。 他想知道将**所有**关闭的窗口粘上所需的**最少**胶带纸的数量。

第一行输入两个整数 $n,m$，表示基督日历的规模。 接下来的 $n$ 行，每行包含 $m$ 个字符，表示基督日历的各个方格。`.` 表示打开的窗口，`#` 表示关闭的窗口。

输出封住所有关闭的窗户所需的最少胶带数量。

**【样例解释 #1】** 一种符合题意的方案：分别在第一列整列、第三列整列和第二行第二列处使用胶带。 **【数据范围】** | Subtask | 分值 | 数据范围及约定 | | :----------: | :----------: | :----------: | | $1$ | $35$ | 每个窗口与至多两个已关闭的窗口相邻 | | $2$ | $35$ | $1 \le n \le 10$ | | $3$ | $40$ | 无 | 对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le m \le 10$。 **【说明】** **本题分值按 COCI 原题设置，满分 $110$。** **题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf) _T4 Selotejp_。**