#P1957. Beehives
Beehives
题目描述:
太郎和花子是生物专业的学生,他们长期致力于对蜂巢的观察研究。他们的兴趣在于发现某一特定野生蜂种的蜂王所产的卵的分布模式。据说蜂王会在短时间内产下一批卵。太郎和花子从未亲眼见过蜂王产卵的过程。因此,每次他们发现蜂巢时,看到的都是刚刚产在蜂巢巢室里的卵。
太郎和花子有一个记录卵的分布布局的惯例:他们假定蜂王产卵时,会沿着一条没有回路(循环)的路径,从一个巢室移动到相邻的巢室。他们会记录下有卵的巢室所构成的路径。从生物学角度来说,并不能保证在每种情况下都能找到这样一条无回路的路径。然而,在他们的观察过程中,从未出现过找不到这种无回路路径的情况。
从一个巢室移动到相邻的巢室只有六种可能的方向,他们约定按照逆时针方向用字母 、、、、 和 来表示这六种移动方向,如图 2 所示。因此,图 1 中的卵的分布布局可以记录为 。
太郎和花子各自独立地在森林中对蜂巢进行了调查。他们每个人都有自己接近蜂巢的方法,以保护自己免受可能的蜜蜂攻击。
他们被要求在一个会议上共同汇报工作,并且要分享各自的观察记录以起草一份联合报告。就在这个时候,他们发现了他们惯例中的一个严重问题。他们从未讨论过从绝对意义上来说,哪个方向应该被认定为 ,因此图 2 可能会被看作是,比如说,图 3 或者图 4 的样子。根据观察蜂巢的方向以及所假定的路径,图 1 中所示的布局可能会被记录得有所不同:如果结合图 3 和图 5,可能会记录为 ;如果结合图 4 和图 6,则可能会记录为 。
只能从蜂巢的正面观察蜂巢,而绝不能从背面观察,所以一个卵的分布布局不会与它的镜像相混淆。
由于他们可能独立地观察到了相同的卵的分布布局,所以他们必须在自己的观察记录中找出重复的记录(当然,他们并没有记录每次观察的准确地点和准确时间)。你的任务是编写一个程序来帮助太郎和花子,检查两条观察记录是否来自相同的卵的分布布局。
输入:
输入的第一行包含后续记录对的数量。该数量最多由三位数字表示。
每一对记录由两行卵的分布布局记录和一行包含一个连字符 的行组成。每行卵的分布布局记录由字母 、、、、 和 组成的一个序列构成。请注意,如果由于某种原因蜂王只产了一个卵,那么卵的分布布局记录可能是一个空序列。你可以相信太郎和花子,输入中的任何路径都不会让你访问任何一个巢室超过一次。输入中的任何一行除了上述所描述的字符外不包含其他字符,并且每行最多包含一百个字符。
输出:
对于每一对记录,输出一行内容,内容为 或者 :如果两条记录表示的是相同的卵分布布局,则输出 ;否则,输出 。该行不应包含其他任何字符。
输入数据1
5
faafd
bcbdb
--
bcbdb
bccac
--
faafd
aafdd
--
aaafddd
aaaeff
--
aaedd
aafdd
--
输出数据1
true
true
false
false
false
来源:
日本2001