P10615 [ICPC 2013 WF] Self-Assembly

自动化化学制造正在试验一种称为自组装的过程。在这个过程中，具有天然亲和力的分子被混合在一起，并允许它们自发地组装成更大的结构。但有一个问题：有时分子会自组装成无限大的结构，导致设备故障。 你必须编写一个程序来决定给定的分子集合是否可以组装成一个无限大的结构。你应该做两个简化假设：1）问题仅限于二维，2）集合中的每个分子表示为一个正方形。正方形的四个边代表分子可以连接到其他兼容分子的表面。 在每个测试用例中，你将得到一组分子描述。每种类型的分子由四个两个字符的*连接标签*描述，指示其边缘如何连接到其他分子的边缘。有两种类型的连接标签： - 一个大写字母 $(A, \dots , Z)$ 后跟 $+$ 或 $−$。如果两个边的标签具有相同的字母但符号不同，则它们是兼容的。例如，$A+$ 与 $A-$ 兼容，但与 $A+$ 或 $B-$ 不兼容。 - 两个数字 $00$。带有此标签的边与任何边都不兼容（即使是另一个标记为 $00$ 的边也不兼容）。 假设每种类型的分子都有无限供应，并且可以旋转和反射。随着分子自组装成更大的结构，两个分子的边只有在兼容时才可以相邻。允许边缘（无论其连接标签如何）不连接到任何东西（该边没有相邻分子）。 图 A.1 显示了三种分子类型的示例以及可以从中组装的有限大小结构（使用该分子集也可以组装其他有限结构）。 

输入由一个测试用例组成。一个测试用例由两行组成。第一行包含一个整数 $n(1 \leq n \leq 40 000)$，表示分子类型的数量。第二行包含 $n$ 个八字符的字符串，每个字符串描述一种分子的类型，单个空格分隔。每个字符串由四个两个字符的连接标签组成，按顺时针顺序表示分子的四个边。

如果这组分子类型可以生成一个无限大的结构，则显示单词 `unbounded`。否则，显示单词 `bounded`。 翻译来自于：[ChatGPT](https://chatgpt.com/)。