Responsive image

问题 1662 --[USACO 4.4.3]重叠的图像

1662: [USACO 4.4.3]重叠的图像

时间限制: 1 Sec  内存限制: 64 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

看下面的五张 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 个字母。

输出描述

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

样例输入

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

样例输出

EDABC

来源

[提交][状态]
ACM算法攻关部