AT_xmascon19_f Stamps 1

兔子有一个 $H \times W$ 的矩形格子。格子的第 $i$ 行（$1 \leq i \leq H$）、第 $j$ 列（$1 \leq j \leq W$）的格子称为格子 $(i, j)$。 格子 $(i, j)$ 的初始状态由字符 $S_{i,j}$ 表示，`#` 表示已经被涂黑，`.` 表示尚未被涂黑。 兔子收到了一个圣诞礼物——一个印章。 每次使用这个印章，可以将一个高 $H/2$、宽 $W/2$ 的矩形区域全部涂黑。也就是说，选择整数 $i_0, j_0$ 后，可以将所有满足 $i_0 \leq i < i_0 + H/2$ 且 $j_0 \leq j < j_0 + W/2$ 的格子 $(i, j)$ 全部涂黑。 兔子想用这个印章将所有格子都涂黑。请问最少需要盖几次印章？

输入以如下格式从标准输入读入。 > $H$ $W$ > $S_{1,1} S_{1,2} \ldots S_{1,W}$ > $S_{2,1} S_{2,2} \ldots S_{2,W}$ > $\vdots$ > $S_{H,1} S_{H,2} \ldots S_{H,W}$

输出使所有格子都被涂黑所需的最小印章次数。

### 限制条件 - $2 \leq H, W \leq 1000$ - $H, W$ 均为偶数 - $S_{i,j}$ 仅为 `.` 或 `#` ### 样例解释 1 例如，如下图所示的盖章方式，可以在 $3$ 次内将所有格子涂黑。  由 ChatGPT 4.1 翻译