Description

你正在玩丧尸粉碎（Zombie Smash）这款游戏：你的目标是在墓地中用你可靠的丧尸粉碎器击碎不断从坟墓中冒出的丧尸。墓地被表示为一个平坦的二维网格。每只丧尸会在网格的某个 $(X, Y)$ 单元格中冒出，停留 1000 毫秒（ms），然后又消失回坟墓。任意时刻每个坟墓旁最多只会有一只丧尸。

你可以在 100ms 内移动到当前位置周围 8 个相邻格中的任意一个：也就是说，你可以向正北、正东、正南、正西、东北、东南、西北、西南移动。即使某个格子当前有丧尸占据，你依然可以经过或停在该格子。只要你到达丧尸所在的格子，就可以立即击碎该丧尸，但每次击碎后，你的丧尸粉碎器需要 750ms 冷却，冷却期间你不能再次击碎丧尸，但你可以自由移动。例如，刚刚在 $(0, 0)$ 击碎一只丧尸后：

• 你需要 750ms 才能到达并击碎 $(1, 1)$ 处的丧尸；
• 你需要 2000ms 才能到达并击碎 $(20, 20)$ 处的丧尸。

你在游戏开始时（时间 $=0$）站在 $(0, 0)$。每一关结束后，你想知道如果你玩得最优，这一关你最多能击碎多少只丧尸。

Input Format

第一行为一个整数 $T$，表示测试用例数量。接下来有 $T$ 组测试数据，每组首先一行一个整数 $Z$，表示本关丧尸数量。

接下来 $Z$ 行，每行包含 3 个用空格分隔的整数，描述一只丧尸出现和消失的时间及位置。第 $i$ 行为 $X_i$、$Y_i$、$M_i$，其中：

• $X_i$ 为第 $i$ 只丧尸出现的横坐标，
• $Y_i$ 为第 $i$ 只丧尸出现的纵坐标，
• $M_i$ 为第 $i$ 只丧尸出现的时间（自游戏开始后的毫秒数）。你可以在 $[M_i, M_i+1000]$ 区间内任意时刻到达该格子并且丧尸粉碎器已充能时，立即击碎该丧尸。

Output Format

对于每个测试用例，输出一行 "Case #$c$: $d$"，其中 $c$ 为测试用例编号（从 1 开始），$d$ 为本关你最多能击碎的丧尸数量。

3
4
1 0 0
-1 0 0
10 10 1000
10 -10 1000
3
1 1 0
2 2 0
3 3 0
5
10 10 1000
-10 10 1000
10 -10 1000
-10 -10 1000
20 20 2000

Case #1: 3
Case #2: 2
Case #3: 2

Hint

限制条件

• $1 \leq T \leq 100$
• $-1000 \leq X_i, Y_i \leq 1000$
• $0 \leq M_i \leq 100000000 = 10^8$
• 任意时刻同一格子不会有两只丧尸。换言之，如果某只丧尸在 $(x, y)$ 的 $t$ 时刻出现，则其他在 $(x, y)$ 出现的丧尸要么出现在 $t-1001$ 及更早，要么出现在 $t+1001$ 及更晚。

测试集 1（7 分，结果可见）

• $1 \leq Z \leq 8$

测试集 2（18 分，结果隐藏）

• $1 \leq Z \leq 100$

翻译由 ChatGPT-4.1 完成。