题目描述

Automatic Chemical Manufacturing is experimenting with a process called self-assembly. In this process, molecules with natural affinity for each other are mixed together in a solution and allowed to spontaneously assemble themselves into larger structures. But there is one problem: sometimes molecules assemble themselves into a structure of unbounded size, which gums up the machinery.

You must write a program to decide whether a given collection of molecules can be assembled into a structure of unbounded size. You should make two simplifying assumptions: 1) the problem is restricted to two dimensions, and 2) each molecule in the collection is represented as a square. The four edges of the square represent the surfaces on which the molecule can connect to other compatible molecules.

In each test case, you will be given a set of molecule descriptions. Each type of molecule is described by four two-character connector labels that indicate how its edges can connect to the edges of other molecules. There are two types of connector labels:

• An uppercase letter $(A, \dots , Z)$ followed by $+$ or $−$. Two edges are compatible if their labels have the same letter but different signs. For example, $A+$ is compatible with $A-$ but is not compatible with $A+$ or $B-$.
• Two zero digits $00$. An edge with this label is not compatible with any edge (not even with another edge labeled $00$).

Assume there is an unlimited supply of molecules of each type, which may be rotated and reflected. As the molecules assemble themselves into larger structures, the edges of two molecules may be adjacent to each other only if they are compatible. It is permitted for an edge, regardless of its connector label, to be connected to nothing (no adjacent molecule on that edge).

Figure A.1 shows an example of three molecule types and a structure of bounded size that can be assembled from them (other bounded structures are also possible with this set of molecules).

输入格式

The input consists of a single test case. A test case consists of two lines. The first contains an integer $n(1 \leq n \leq 40 000)$ indicating the number of molecule types. The second line contains $n$ eight-character strings, each describing a single type of molecule, separated by single spaces. Each string consists of four two-character connector labels representing the four edges of the molecule in clockwise order.

输出格式

Display the word unbounded if the set of molecule types can generate a structure of unbounded size. Otherwise, display the word bounded.

题目大意

【题目描述】

自动化化学制造正在试验一种称为自组装的过程。在这个过程中，具有天然亲和力的分子被混合在一起，并允许它们自发地组装成更大的结构。但有一个问题：有时分子会自组装成无限大的结构，导致设备故障。

你必须编写一个程序来决定给定的分子集合是否可以组装成一个无限大的结构。你应该做两个简化假设：1）问题仅限于二维，2）集合中的每个分子表示为一个正方形。正方形的四个边代表分子可以连接到其他兼容分子的表面。

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

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

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

图 A.1 显示了三种分子类型的示例以及可以从中组装的有限大小结构（使用该分子集也可以组装其他有限结构）。

【输入格式】

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

【输出格式】

如果这组分子类型可以生成一个无限大的结构，则显示单词 unbounded。否则，显示单词 bounded。

翻译来自于：ChatGPT。

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

bounded

1
K+K-Q+Q

unbounded