AT_xmascon19_g.Stamps 2

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

兔子有一个 $H \times W$ 的矩形网格。网格中第 $i$ 行（ $1 \le i \le H$ ）、第 $j$ 列（ $1 \le j \le W$ ）上的格子称为格子 $(i, j)$ 。

每个格子 $(i, j)$ 的初始状态由字符 $S_{i,j}$ 表示，其中 # 表示已涂黑，而 . 表示未涂黑。

作为圣诞礼物，兔子收到了一个印章套装。

这个套装包含两种类型的印章，每种印章可以一次性将结构如图所示的一组格子全部涂黑。

印章图示

具体来说：

使用左侧的印章一次，可以选择一个基点 $(i_0, j_0)$ ，然后将所有满足 $i = i_0 + 5a + 2b$ 和 $j = j_0 - 2a + 5b$ 的格子 $(i, j)$ 涂黑，其中 $a, b$ 为整数。
使用右侧的印章一次，也可以选择一个基点 $(i_0, j_0)$ ，涂黑所有满足 $i = i_0 + 2a + 5b$ 和 $j = j_0 - 5a + 2b$ 的格子 $(i, j)$ ，其中 $a, b$ 为整数。

兔子希望利用这套印章将整个网格的所有格子都涂黑。问最少需要盖多少次印章？

输入格式

输入通过标准输入提供，并采用如下格式：

$H\, W$
$S_{1,1} S_{1,2} \ldots S_{1,W}$
$S_{2,1} S_{2,2} \ldots S_{2,W}$
$\vdots$
$S_{H,1} S_{H,2} \ldots S_{H,W}$

输出格式

请输出将网格中所有格子涂黑所需的最少印章次数。

数据范围

$1 \le H, W \le 300$
$S_{i,j}$ 可能是 . 或 #。

本翻译由 AI 自动生成

输入输出样例

输入#1

8 8
.####.##
########
.####.##
########
########
##.####.
########
##.####.

输出#1

输入#2

50 50
######################.#.##.######################
##############.########################.###..#####
####.###############..############################
###################.###########.####.#############
########.#.#####################.##########..#####
###.###.#####.######.######.##############.###.##.
.########.###.###############..#######.###.####.#.
.#.###############.######.#####.###############..#
####.########################.###.##.#############
################.#####.#.#########.#.#############
..#########.############.#########.#####.######.##
######.###############.#####.###########..########
###.##########.#.##########..################.####
################.###########################.##.##
#####.############.....#####.####..###############
#.#####################.####.#.######..##########.
#########.#.########.#.###.############.##.#######
########.####.####################.#######.#..####
##.#####.####.################.#######.#######.###
..#######.#.#################.###.##############..
#.######.####.#####.#.####.#####.##.#####..#######
################.#######..#####.##################
########.###..#########..###.########.###.######.#
#############################.######.###########.#
##..#############.#############..#########.####.##
############.###########.###.##############..#####
.#####..###############.#########.#.#########.####
#.########.############.#########.############.###
###.#.####################..###########.#..#######
#####.###.##############.##.##########.#####.#####
#######.##.#####.##########.###############.######
.#########.################.#####.#########.######
##.############.###..###########.###.#.##.######.#
##############..#######.#############.######.#####
###.################.###..######.##..#########.###
#.##################.########.########..##########
.#.#########.#####################################
#######.###########.#########.#####.############..
#.####################.##..###.###.###############
###########.############.####..###################
.###########.#########.#################.#########
##############.#..##############..#########.######
###..##.##########################.###########.###
#########.##########.#.#####.####.################
#.######.##.################.#.######.#.#####.####
#########.######.###.#.###.######.###.#.#####.####
###############.##################.#######.#..####
#.######.#######..#############..#########.##.####
#########.###########.####.###########.#########.#
######.#.###########.#####.###.##.#######..######.

输出#2

输入#3
```
1 1
#
```
输出#3
```
0
```

输入解题思路，AI测评打分。不知道怎么写?

首页