CF2069B.Set of Strangers

普及-

通过率：0%

AC君温馨提醒

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

给定一个包含 $n$ 行 $m$ 列的表格。初始时，第 $i$ 行第 $j$ 列的单元格颜色为 $a_{i, j}$ 。

我们称两个单元格是陌生人（strangers）如果它们不共享任何一条边（允许通过角落接触）。

我们称一个单元格集合为陌生人集合（set of strangers），当且仅当集合中任意两个单元格都是陌生人。根据定义，包含不超过一个单元格的集合总是陌生人集合。

在每一步操作中，你可以选择一个满足以下条件的陌生人集合：集合中所有单元格颜色相同，并将它们全部涂成另一种颜色（可以选择任意一种颜色作为结果颜色）。

问：要将整个表格涂成同一种颜色，最少需要多少步操作？

第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ）——测试用例的数量。接下来输入 $t$ 个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ （ $1 \le n \le m \le 700$ ）——表格的行数和列数。

接下来的 $n$ 行，每行包含对应行的单元格颜色 $a_{i, 1}, \dots, a_{i, m}$ （ $1 \le a_{i, j} \le nm$ ）。

保证所有测试用例的 $nm$ 总和不超过 $5 \cdot 10^5$ 。

对于每个测试用例，输出一个整数——将表格所有单元格涂成同一种颜色所需的最少操作步数。

输入#1

4
1 1
1
3 3
1 2 1
2 3 2
1 3 1
1 6
5 4 5 4 4 5
3 4
1 4 2 2
1 4 3 5
6 6 3 5

输出#1

在第一个测试用例中，表格初始时已经是同一种颜色。

在第二个测试用例中，例如可以先选择所有颜色为 $1$ 的单元格并将其涂成 $3$ ，然后选择所有颜色为 $2$ 的单元格也涂成 $3$ 。

在第三个测试用例中，可以选择所有颜色为 $5$ 的单元格并将其涂成 $4$ 。

翻译由 DeepSeek R1 完成

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