← 返回题目列表

AtCoder · xmascon19_f

F. 邮票 1

中文机器翻译题面 查看原题

配点 : 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 次内将所有方块涂成黑色。

b50ca03a62fb58d6362e2ea94e6d1e7d.png


入力例 2

2 6
######
######

出力例 2

0