P2741 [USACO4.4]重叠的图像Frame Up

    • 311通过
    • 1K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    9 8
    .CCC....
    ECBCBB..
    DCBCDB..
    DCCC.B..
    D.B.ABAA
    D.BBBB.A
    DDDDAD.A
    E...AAAA
    EEEEEE..
    输出样例#1: 复制
    EDABC

    说明

    题目翻译来自NOCOW。

    USACO Training Section 4.4

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。