← 返回题目列表

AtCoder · xmascon19_i

I. 邮票 4

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

配点 : 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 次按下后,可以像下图那样将格子集合全部涂成黑色。 关于下图更详细的说明是,被红框围住的 19 \times 31 模式沿对角线无限连接。 但是,印章只能像下图那样以格子为单位平移后按下,不能旋转、翻转或错位按下等。 1 只能以单元格为单位平行移动并推动,无法旋转或翻转 0.5 不能错位按压等。

8e24b77d1614516c3b7ae022a7aabb89.png

兔子打算使用这个印章,将尚未涂色的格子全部涂成黑色。最少需要按几次印章呢?

制約

  • 1 \le H,W \le 1000
  • 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

19 31
..#############################
#...###########################
###..##########################
####...########################
######...######################
########..#####################
#########...###################
###########...#################
#############..################
##############...##############
################..#############
#################...###########
###################...#########
#####################..########
######################...######
########################...####
##########################..###
###########################...#
#############################..

出力例 1

1

入力例 2

5 5
###.#
##..#
##.##
#..##
#.###

出力例 2

4

入力例 3

20 19
###.###########.###
##.########...##.##
###.##############.
###################
######.############
##############.#.##
#########.#########
#######.#########.#
##########.#######.
#########.#.#.#.###
#######.###########
#####.#############
.#.##.#############
###.#######.####.#.
.########.#.#######
##.################
#.####.############
########.#.########
###################
#.#.########.######

出力例 3

13