一个让人感觉很复杂的BFS（但是并不很复杂）

问题 D: BFS_连连看游戏

时间限制: 2 Sec 内存限制: 5 MB

提交: 12 解决: 3

[提交][状态][讨论版]

题目描述

大 家都玩过连连看吧！今天我们玩一个类似的游戏。在一个由10*10个小方格组成的矩形里有n(n<=10)对字符(它们是大写字符中的前n个)。矩 形里有些位置是可以从上面走过，有些则不能。能走过的位置用'.'标识，不能的用'#'标识。如果2个相同字符是连通的(从一个字符能走到另一个字符，注 意走的时候只能向上、下、左、右走。某个位置是有其他字符时，这个位置是不能走的)，那么这对字符能够进行配对。如果将这对字符配对，这对字符将从这个矩 形里消除，也就是说这2个字符所在的位置对于其他字符而言变成能走动了。

现在的问题是：请你决定这些字符的配对顺序(只有能配对才能进行配对)，使得n对字符最后都配对成功。

输入

先给出一个正整数t(t<=10)，表示有t组测试数据。

每组测试数据有10行组成，每行有10个字符。这些字符只能是'.'，'#'，或者是大写字符中的前n个。每组测试数据中不超过10对字符。

输出

如果能够使每组测试数据中的n对字符配对成功，输出配对的顺序。如果有多种配对成功的顺序，输出字典序最小的那组。

否则输出"My God!"。

样例输入

2

ABF.......

CE........

D.........

..........

..........

..........

..........

.........D

........EC

.......FBA

ABF.......

CE........

D.........

..........

…… …… 余下全文