← 返回题目列表

AtCoder · xmascon19_g

G. 邮票 2

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

配点 : 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 种印章,每种可以一次性将下图中的格子集合涂黑。

2634fdc1c331a3ef57daf72b5bc2be7f.png

也就是说,

  • 左边的印章 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