P13452 [GCJ 2009 Finals] Marbles

在一个方格坐标系上，你有 $2n$ 个弹珠。这些弹珠被涂成 $n$ 种不同的颜色，每种颜色恰好有 $2$ 个弹珠。所有弹珠被依次放在坐标 $(1,0)$、$(2,0)$、$\ldots$、$(2n, 0)$ 上。 你的任务是为每种颜色画一条路径，将该颜色的两个弹珠连接起来。每条路径应由若干条垂直或水平的线段组成，且这些线段必须连接在网格点上。任意两条路径不能相交或相触。任意一条路径都不能穿过 $y=0$ 这条直线。每条路径只能在它所连接的两个弹珠的位置与 $y=0$ 相接，因此每条路径的首尾线段必须是竖直的。 给定弹珠的排列方式，返回一个解方案的最小高度，如果不存在合法解，则返回 $-1$。高度定义为所有路径所经过的最大 $Y$ 坐标与最小 $Y$ 坐标之差。 例如： ``` red red blue yellow blue yellow ``` 一种可行的解法如下： ``` +---+ +-----------+ | | | | red red blue yellow blue yellow | | +-----------+ ``` 在这个例子中，最小高度为 $2$。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组的第一行为 $n$，表示弹珠颜色种类数。下一行为 $2n$ 个用空格分隔的单词，按从左到右顺序分别表示每个弹珠的颜色。每个颜色由小写字母（'a' 到 'z'）组成，长度不超过 $10$ 个字符。每种颜色恰好出现两次。

对于每组测试数据，输出一行，格式如下： Case #$x$: 其中 $x$ 是测试编号（从 $1$ 开始），后接一个最优解的最小高度。如果不存在合法解，输出 $-1$。

**限制条件** - $1 \leq T \leq 50.$ **小数据集（7 分）** - 时间限制：3 秒 - $1 \leq n \leq 20.$ **大数据集（32 分）** - 时间限制：6 秒 - $1 \leq n \leq 500.$ 翻译由 ChatGPT-4.1 完成。