P2741 [USACO4.4] Frame Up

Look at the following five $9 \times 8$ images: ```plain ........ ........ ........ ........ .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, stack these images from bottom to top in the order $1\sim 5$, with image 1 at the bottom and image 5 at the top. If one image covers another, then part of the image underneath becomes invisible. This yields the following image: ```plain .CCC.... ECBCBB.. DCBCDB.. DCCC.B.. D.B.ABAA D.BBBB.A DDDDAD.A E...AAAA EEEEEE.. ``` For such an image, compute the stacking order of the rectangular images from bottom to top. The rules are as follows: - The width of each rectangle border is $1$, and each side has length at least $3$. - For each rectangle, at least part of each of its four sides is visible. Note that a corner belongs to two sides. - Rectangles are denoted by uppercase letters, and the letter used for each rectangle is unique.

The first line contains two integers separated by a space: the image height $H$ and image width $W$ ($3 \le H,W \le 30$). The next $H$ lines each contain $W$ letters: the final overlapped image.

Output the letters in order from bottom to top. If there is more than one valid ordering, output each ordering in lexicographic order, one per line. The testdata guarantees at least one solution. The number of solutions does not exceed $10000$.

Translation from NOCOW. USACO Training Section 4.4. Translated by ChatGPT 5