自组装 - 题目

自动化学制造公司正在试验一种称为“自组装”的工艺。在此过程中，具有天然亲和力的分子在溶液中混合，并允许它们自发地组装成更大的结构。但存在一个问题：有时分子会组装成无限大的结构，这会堵塞机器。

你需要编写一个程序来判断给定的分子集合是否可以组装成无限大的结构。你应该做出两个简化假设：1) 问题限制在二维空间，2) 集合中的每个分子都表示为一个正方形。正方形的四条边代表分子可以与其他兼容分子连接的表面。

在每个测试用例中，你将获得一组分子描述。每种类型的分子由四个双字符连接器标签描述，这些标签指示其边缘如何与其他分子的边缘连接。连接器标签有两种类型：

一个大写字母（$A, \dots, Z$）后跟 $+$ 或 $-$。如果两个标签的字母相同但符号不同，则它们是兼容的。例如，$A+$ 与 $A-$ 兼容，但与 $A+$ 或 $B-$ 不兼容。
两个零字符 $00$。带有此标签的边缘与任何边缘都不兼容（甚至与另一个标记为 $00$ 的边缘也不兼容）。

假设每种类型的分子都有无限供应，并且可以旋转和翻转。当分子组装成更大的结构时，两个分子的边缘只有在兼容时才能相邻。允许边缘（无论其连接器标签如何）不与任何东西连接（该边缘没有相邻分子）。

图 A.1 展示了三种分子类型的示例以及可以由它们组装成的有限大小的结构（使用这组分子也可以组装出其他有限结构）。

图 A.1：样例输入 1 的说明。

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

如果分子类型集合可以生成无限大的结构，则输出单词 unbounded。否则，输出单词 bounded。

3
A+00A+A+ 00B+D+A- B-C+00C+

bounded

1
K+K-Q+Q-

unbounded

QOJ.ac