问题 C: [STT2024WC+] 魔王军的扩张
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：3
题目描述
### 题目背景
七魔下昆仑后，重新为祸人间，同时组建起了势力庞大的魔王军。魔王军烧杀抢掠，遇村屠村，一个不留。
### 题目描述
人间平原的大小为 $n \times m$，每个地方的地形可以用字符表示，`.`表示这个地方为村子，`*`表示有大石头。魔王军的行进过程类似国际象棋中的马，走的是 $1 \times 2$ 的格子。
魔王军可以从任意村庄出发，由于军队管理严格，所有魔王军只能从上往下征战，不能回头。魔王军不能踩石头，并且不会再去被之前的魔王军征服过的村子。问最少需要派遣多少支魔王军，才能征服整个人间平原？
输入
第一行两个正整数 $n,m$，表示人间平原的大小。
接下来 $n$ 行，每行 $m$ 个字符 $a_{i,j}$。表示这个地区的地形。
接下来 $n$ 行，每行 $m$ 个字符 $a_{i,j}$。表示这个地区的地形。
输出
一个整数，表示至少需要派遣多少支魔王军。
样例输入 复制
3 3
...
.*.
...样例输出 复制
4提示
**【数据范围】**
对于 $40\%$ 的数据，$1 \leq n,m \leq 10$。
对于 $100\%$ 的数据，$1 \leq n,m \leq 100$。