配点 : 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} 灯泡时# 被漆成黑色,. 表示未涂漆。
兔子作为圣诞礼物收到了印章套装。
只兔子作为圣诞礼物收到了一套邮票。 2 种印章,每种可以一次性将下图中的格子集合涂黑。
也就是说,
- 左边的印章 1 按下回车后,有整数 i_0,j_0 时, 满足i = i_0+5a+2b, j = j_0-2a+5b 对于 a,b 存在的方格 (i,j) 涂成黑色。
- 右边的印章 1 按下回车后,有整数 i_0,j_0 时, 满足i = i_0+2a+5b, j = j_0-5a+2b 对于 a,b 存在的方格 (i,j) 涂成黑色。
兔子想用这个印章套装将所有方格涂黑。 最少需要按多少次印章呢?
制約
- 1 \le H,W \le 300
- 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
8 8 .####.## ######## .####.## ######## ######## ##.####. ######## ##.####.
出力例 1
3
入力例 2
50 50 ######################.#.##.###################### ##############.########################.###..##### ####.###############..############################ ###################.###########.####.############# ########.#.#####################.##########..##### ###.###.#####.######.######.##############.###.##. .########.###.###############..#######.###.####.#. .#.###############.######.#####.###############..# ####.########################.###.##.############# ################.#####.#.#########.#.############# ..#########.############.#########.#####.######.## ######.###############.#####.###########..######## ###.##########.#.##########..################.#### ################.###########################.##.## #####.############.....#####.####..############### #.#####################.####.#.######..##########. #########.#.########.#.###.############.##.####### ########.####.####################.#######.#..#### ##.#####.####.################.#######.#######.### ..#######.#.#################.###.##############.. #.######.####.#####.#.####.#####.##.#####..####### ################.#######..#####.################## ########.###..#########..###.########.###.######.# #############################.######.###########.# ##..#############.#############..#########.####.## ############.###########.###.##############..##### .#####..###############.#########.#.#########.#### #.########.############.#########.############.### ###.#.####################..###########.#..####### #####.###.##############.##.##########.#####.##### #######.##.#####.##########.###############.###### .#########.################.#####.#########.###### ##.############.###..###########.###.#.##.######.# ##############..#######.#############.######.##### ###.################.###..######.##..#########.### #.##################.########.########..########## .#.#########.##################################### #######.###########.#########.#####.############.. #.####################.##..###.###.############### ###########.############.####..################### .###########.#########.#################.######### ##############.#..##############..#########.###### ###..##.##########################.###########.### #########.##########.#.#####.####.################ #.######.##.################.#.######.#.#####.#### #########.######.###.#.###.######.###.#.#####.#### ###############.##################.#######.#..#### #.######.#######..#############..#########.##.#### #########.###########.####.###########.#########.# ######.#.###########.#####.###.##.#######..######.
出力例 2
15
入力例 3
1 1 #
出力例 3
0