配点 : 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 不能错位按压等。
兔子打算使用这个印章,将尚未涂色的格子全部涂成黑色。最少需要按几次印章呢?
制約
- 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