好的，这是整理好的题面，不含解题思路，只包含样例解释。

题目描述

在一块 $N \times M$ 的网格状地面上，一些格子是泥泞的（用 * 表示），其他格子是干净的（用 . 表示）。

需要用一些宽度为 1、长度任意的木板把所有泥地盖住，不能盖住干净的地面。
木板必须沿着网格方向放置（水平或垂直），覆盖若干个完整的格子，木板可以重叠。

求最少需要多少块木板。

输入格式

第一行两个整数 $N$ 和 $M$。
接下来 $N$ 行，每行 $M$ 个字符（* 或 .），表示地面情况。

输出格式

输出一个整数，表示最少需要的木板数量。

数据范围

$1 \le N,M \le 50$

输入样例

4 4
*.*.
.***
***.
..*.

输出样例

4

样例解释

地面网格：

* . * .
. * * *
* * * .
. . * .

* 表示泥泞，需要覆盖。

木板覆盖规则

木板宽度为 1，长度任意，可以水平或竖直放置。
目标是用最少木板覆盖所有 *。

一种可行方案（用 4 块木板）：

1. 第一行：第一块水平木板覆盖第 1 列的泥地（(1,1) 和 (3,1) 在不同行，不能水平覆盖在一起，所以要分开考虑），我们直接找最优方案：

尝试：

• 竖板覆盖第 1 列：覆盖 (1,1) 和 (3,1) → 1 块板。
• 竖板覆盖第 3 列：覆盖 (1,3), (2,3), (3,3), (4,3) → 1 块板。
• 横板覆盖第 2 行：覆盖 (2,2), (2,3), (2,4) → 1 块板。
• 横板覆盖第 3 行：覆盖 (3,1), (3,2), (3,3) → 1 块板。

检查是否全覆盖：

• (1,1)：竖板 1 列
• (1,3)：竖板 3 列
• (2,2)：横板 2 行
• (2,3)：横板 2 行 或 竖板 3 列
• (2,4)：横板 2 行
• (3,1)：横板 3 行
• (3,2)：横板 3 行
• (3,3)：横板 3 行 或 竖板 3 列
• (4,3)：竖板 3 列

全被覆盖。总共 4 块木板。

能否用 3 块？
假设用 3 块，每块必须覆盖尽可能多的泥地。
考虑泥地分布，似乎需要至少 4 块才能全部覆盖（可以通过二分图最小覆盖证明）。

所以最少为 4。

输出 4。