10443 - 重叠的图像

看下面的五张 9 x 8 的图像：

........ ........ ........ ........ .CCC.... EEEEEE.. ........ ........ ..BBBB.. .C.C.... E....E.. DDDDDD.. ........ ..B..B.. .C.C.... E....E.. D....D.. ........ ..B..B.. .CCC.... E....E.. D....D.. ....AAAA ..B..B.. ........ E....E.. D....D.. ....A..A ..BBBB.. ........ E....E.. DDDDDD.. ....A..A ........ ........ E....E.. ........ ....AAAA ........ ........ EEEEEE.. ........ ........ ........ ........

1 2 3 4 5

现在，把这些图像按照 1—5 的编号从下到上重叠，第 1 张在最下面，第 5 张在最顶端。如果一张图像覆盖了另外一张图像，那么底下的图像的一部分就变得不可见了。我们得到下面的图像：

        .CCC....
       ECBCBB..
       DCBCDB..
       DCCC.B..
       D.B.ABAA
       D.BBBB.A
       DDDDAD.A
       E...AAAA
       EEEEEE..

对于这样一张图像，计算构成这张图像的矩形图像从底部到顶端堆叠的顺序。

下面是这道题目的规则：

矩形的边的宽度为 1 ，每条边的长度都不小于 3 。 矩形的每条边中，至少有一部分是可见的。注意，一个角同时属于两条边。 矩形用大写字母表示，并且每个矩形的表示符号都不相同。

第一行 两个用空格分开的整数：图像高 H (3 <= H <=30) 和图像宽 W (3 <= W <= 30) 。

第二行到第 H+1 行 H 行，每行 W 个字母。

按照自底向上的顺序输出字母。如果有不止一种情况，按照字典顺序输出每一种情况（至少会有一种合法的顺序）。

Frame Up

Consider the following five picture frames shown on an 9 x 8 array:

........ ........ ........ ........ .CCC.... EEEEEE.. ........ ........ ..BBBB.. .C.C.... E....E.. DDDDDD.. ........ ..B..B.. .C.C.... E....E.. D....D.. ........ ..B..B.. .CCC.... E....E.. D....D.. ....AAAA ..B..B.. ........ E....E.. D....D.. ....A..A ..BBBB.. ........ E....E.. DDDDDD.. ....A..A ........ ........ E....E.. ........ ....AAAA ........ ........ EEEEEE.. ........ ........ ........ ........

1 2 3 4 5

Now place all five picture frames on top of one another starting with 1 at the bottom and ending up with 5 on top. If any part of a frame covers another frame, it hides that part of the frame below. Viewing the stack of five frames we see the following.

       .CCC...
       ECBCBB..
       DCBCDB..
       DCCC.B..
       D.B.ABAA
       D.BBBB.A
       DDDDAD.A
       E...AAAA
       EEEEEE..

Given a picture like this, determine the order of the frames stacked from bottom to top.

Here are the rules for this challenge:

The width of the frame is always exactly 1 character and the sides are never shorter than 3 characters. It is possible to see at least one part of each of the four sides of a frame. A corner is part of two sides. The frames will be lettered with capital letters, and no two frames will be assigned the same letter. PROGRAM NAME: frameup INPUT FORMAT Line 1: Two space-separated integers: the height H (3 <= H <=30) and the width W (3 <= W <= 30).
Line 2..H+1: H lines, each with a string W characters wide.

SAMPLE INPUT (file frameup.in) 9 8 .CCC.... ECBCBB.. DCBCDB.. DCCC.B.. D.B.ABAA D.BBBB.A DDDDAD.A E...AAAA EEEEEE..

OUTPUT FORMAT Print the letters of the frames in the order they were stacked from bottom to top. If there are multiple possibilities for an ordering, list all such possibilities -- in alphabetical order -- on successive lines. There will always be at least one legal ordering.

SAMPLE OUTPUT (file frameup.out) EDABC