P13149 [GCJ 2018 #3] Field Trip

一所小学的 $N$ 个人——一名老师和 $N-1$ 名学生——正在进行一次郊游。他们正在探索一片无限大的二维网格草地，每个格子为单位格。每个人当前都占据着某一个格子；同一个格子上可能有多个人。 当要回家时，老师和学生们必须全部聚集到同一个格子里；具体是哪个格子无所谓，因为他们的校车可以在任何地方接他们。学生们已经学会了一种便于集合的算法： - 老师编号为 1，学生编号为 2 到 $N$。 - 每个人的一个动作可以是移动到与当前格子至少共享一个边或一个角的 8 个格子中的任意一个，或者选择留在原地不动。 - 当郊游结束的信号响起时，老师会检查所有 $N$ 个人是否都在同一个格子里。如果是，则不需要再做任何操作。否则，老师开始一轮操作： 1. 首先，老师进行一次动作，如上所述。老师可以自行决定是否移动以及移动到哪里。 2. 然后，每个学生依次进行动作，从 2 号学生开始，依次到第 $N$ 号学生；第 $i$ 个学生要等到第 $i-1$ 个人完成动作后才能行动。学生的动作是确定的：第 $i$ 个学生必须选择能使自己与第 $i-1$ 个人的格子中心距离最小的选项。这种选择不会有歧义，9 个选项中必有唯一一个能最小化该距离。 - 一轮操作结束后，老师再次检查所有人是否都在同一个格子里。如果还没有，则开始新的一轮操作，如此反复，直到所有人都在同一个格子里为止。 如果老师每次都做出能最小化轮数的选择，最少需要多少轮才能集合所有人？

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为一个整数 $N$，表示郊游的人数。接下来的 $N$ 行中，第 $i$ 行包含两个整数 $R_i$ 和 $C_i$，表示第 $i$ 个人（老师为第 1 个人）初始所在的格子的行号和列号。

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为最少需要的轮数。

**样例解释** 在样例 1 中，老师在 $(3, 2)$，即第 3 行第 2 列。2 号学生在 $(0, 2)$，3 号学生在 $(0, 0)$。老师的一种最优策略如下： - 第 1 轮： - 老师移动到 $(2, 2)$。 - 2 号学生移动到 $(1, 2)$。 - 3 号学生移动到 $(1, 1)$。 - 第 2 轮： - 老师移动到 $(1, 2)$。 - 2 号学生留在 $(1, 2)$。 - 3 号学生移动到 $(1, 2)$。此时所有人都在同一个格子。 在样例 2 中，老师和两名学生一开始就在同一个格子里，因此不需要任何轮数。 在样例 3 中，老师可以原地不动，所有学生在第一轮结束时都会移动到老师所在的格子。 在样例 4 中，老师应当沿对角线移动 4 次到达 $(4, 4)$。 在样例 5 中，老师应当先移动到 $(1, 1)$；然后 2、3、4 号学生都会移动到 $(1, 2)$。注意，虽然所有学生都在同一个格子，但老师还不在，因此需要再进行一轮。在第二轮中，老师可以移动到 $(1, 2)$ 与学生们会合，学生们则不动。 **数据范围** - $1 \leq T \leq 100$。 **测试点 1（4 分，公开）** - $2 \leq N \leq 10$。 - $0 \leq R_i \leq 8$，对所有 $i$。 - $0 \leq C_i \leq 8$，对所有 $i$。 **测试点 2（10 分，隐藏）** - $2 \leq N \leq 10^4$。 - $0 \leq R_i \leq 10^9$，对所有 $i$。 - $0 \leq C_i \leq 10^9$，对所有 $i$。 由 ChatGPT 4.1 翻译