AT_2_stpc2025_2_j.KinGin's Summit

有一个无限大的二维网格。

在网格上有 $N$ 个人，第 $i$ 个人初始位于格点 $(R_i, C_i)$。每个人都戴着金色或银色的帽子。当 $H_i =\texttt{G}$ 时，第 $i$ 个人戴着金色帽子；当 $H_i =\texttt{S}$ 时，戴着银色帽子。

每一回合，每个人会根据帽子的颜色，从当前位置按如下方式移动：

• 戴金色帽子的人：
  可以原地不动，或者像将棋中的金将一样移动。具体来说，若当前位于 $(i, j)$，则可移动到格点 $(i-1, j-1),\ (i-1, j),\ (i-1, j+1),\ (i, j-1),\ (i, j),\ (i, j+1),\ (i+1, j)$ 中的任一格。
• 戴银色帽子的人：
  可以原地不动，或者像将棋中的银将一样移动。具体来说，若当前位于 $(i, j)$，则可移动到格点 $(i-1, j-1),\ (i-1, j),\ (i-1, j+1),\ (i, j),\ (i+1, j-1),\ (i+1, j+1)$ 中的任一格。

请你求出，为了让所有 $N$ 个人汇聚到同一个格点，所需的最小回合数。

有 $T$ 组测试数据，分别输出每组数据的答案。

输入按照以下格式给出。

$T\ \mathrm{case}_1\ \mathrm{case}_2\ \cdots\ \mathrm{case}_T$

其中，$\mathrm{case}_i$ 表示第 $i$ 个测试用例，每一组测试如下格式：

$N$ $R_1$ $C_1$ $H_1$
$R_2$ $C_2$ $H_2$
$\vdots$
$R_N$ $C_N$ $H_N$

请对每个测试用例按照顺序输出一行答案。

部分分

如果你能解决 $H_i = \texttt{G}$ 的数据集（仅有金帽），可获得 $30$ 分。

样例解释 1

对于第 $1$ 个测试用例，例如可以按如下方式移动，在 $2$ 回合内所有人汇聚到同一格：

• 第 $1$ 回合
  • 第 $1$ 个人走到 $(2, 2)$
  • 第 $2$ 个人走到 $(3, 3)$
• 第 $2$ 回合
  • 第 $1$ 个人留在原地
  • 第 $2$ 个人走到 $(2, 2)$

对于第 $2$ 个测试用例，例如可以按如下方式移动，在 $2$ 回合内所有人汇聚到同一格：

• 第 $1$ 回合
  • 第 $1$ 个人走到 $(1, 2)$
  • 第 $2$ 个人走到 $(1, 3)$
  • 第 $3$ 个人走到 $(1, 2)$
• 第 $2$ 回合
  • 第 $1$ 个人留在原地
  • 第 $2$ 个人走到 $(1, 2)$
  • 第 $3$ 个人留在原地

对于第 $3$ 个测试用例，所有人一开始就在同一格。

样例解释 2

对于第 $1$ 个测试用例，例如可以按如下方式移动，在 $2$ 回合内所有人汇聚到同一格：

• 第 $1$ 回合
  • 第 $1$ 个人走到 $(2, 1)$
  • 第 $2$ 个人走到 $(2, 2)$
• 第 $2$ 回合
  • 第 $1$ 个人留在原地
  • 第 $2$ 个人走到 $(2, 1)$

这个输入样例满足部分分的限制。

约束条件

• $T, N, R_i, C_i$ 为整数
• $1 \le T \le 10^5$
• $1 \le N \le 2 \times 10^5$
• $1 \le R_i \le 10^9$
• $1 \le C_i \le 10^9$
• $H_i$ 为 G 或 S
• 所有测试用例的 $N$ 之和不超过 $2\times 10^5$

由 ChatGPT 5 翻译