配点 : 100 点
除了图章类型和约束之外,图章 1 至 4 具有相同的问题设置。
問題文
兔子是 它有一个矩形网格 H \times W 。 从网格上方 i 行目 (1 \le i \le H),从左起 j 列目 (1 \le j \le W) (i,j) 。
马斯 (i,j) 的初始状态是字符 S_{i,j} 其表示为# 被漆成黑色,. 表示未涂漆。
兔子收到了一张邮票作为圣诞礼物。
此邮票 1 垂直按 H/2 广场旁边 W/2 您可以用黑色填充正方形大小的矩形。 也就是说,一个整数 i_0,j_0 时, 满足i_0 \le i \lt i_0+H/2 和 j_0 \le j \lt j_0+W/2 的正方形 您可以将所有 (i,j) 涂成黑色。
兔子试图用这个图章把所有的方块都涂成黑色。 我最少应该盖章多少次?
制約
- 2 \le H,W \le 1000
- H,W 均为偶数
- S_{i,j} 是
.或#
入力
输入将以以下格式从标准输入提供。
H W
S_{1,1}S_{1,2}...S_{1,W}
S_{2,1}S_{2,2}...S_{2,W}
:
S_{H,1}S_{H,2}...S_{H,W}
出力
打印将所有方块涂成黑色所需的最少印章数量。
入力例 1
4 4 #..# #.#. ..## ..##
出力例 1
3
例如,如果按如下所示, 您可以在 3 次内将所有方块涂成黑色。
入力例 2
2 6 ###### ######
出力例 2
0