AT_wupc2019_b.10 puzzle

通过率：0%

AC君温馨提醒

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

题目描述

有一个高为 $H$ 、宽为 $W$ 的网格。初始时，第 $i$ 行第 $j$ 列的格子上写有一个 $0$ 到 $9$ 之间的整数 $A_{i,j}$ 。网格中的格子与其共享边的格子相邻。这里，某个格子的子集被称为“连通”的，指的是对于集合中任意一对格子，都可以通过只经过集合中相邻的格子多次移动而互相到达。

加藤君可以进行如下操作 $0$ 次或多次：

选择一个“连通”的格子子集，设该集合中格子上写的数的最大值为 $M$ ，然后将该集合中所有格子上的数都改写为 $2 \times M$ 除以 $10$ 的余数。

请判断加藤君是否能够将网格中所有格子上的数都变为 $0$ 。如果可以，请求出实现这一目标所需的最小操作次数。

输入格式

输入通过标准输入按以下格式给出。

$H$ $W$
$A_{1,1}\ A_{1,2}\ \dots\ A_{1,W}$
$A_{2,1}\ A_{2,2}\ \dots\ A_{2,W}$
$\vdots$
$A_{H,1}\ A_{H,2}\ \dots\ A_{H,W}$

输出格式

如果可以将所有格子上的数都变为 $0$ ，请输出如下格式的 Yes 和最小操作次数 $N$ ：

Yes $N$

如果无法实现，请输出 No。

输入输出样例

输入#1
```
2 3
0 1 2
3 4 5
```
输出#1
```
Yes 1
```
输入#2
```
2 2
1 2
2 1
```
输出#2
```
No
```
输入#3
```
5 3
6 6 6
6 5 5
6 6 6
6 5 6
6 6 6
```
输出#3
```
Yes 2
```
输入#4
```
3 3
1 2 3
4 5 6
7 8 9
```
输出#4
```
Yes 4
```

说明/提示

限制条件

$1 \leq H,W \leq 100$
$0 \leq A_{i,j} \leq 9$
输入的所有值均为整数。

样例解释 1

例如，如果选择所有格子作为集合，则 $M=5$ 。 $2 \times M=10$ ， $10$ 除以 $10$ 的余数为 $0$ ，因此可以将所有格子上的数都改写为 $0$ 。所以只需 $1$ 次操作即可达成目标。

样例解释 2

无论如何操作，都无法达成目标。

样例解释 3

例如，首先选择所有写有 $6$ 的格子作为集合（这是“连通”的），对其进行操作后，再选择所有格子作为集合进行操作，这样只需 $2$ 次操作即可达成目标。

由 ChatGPT 4.1 翻译

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

首页