TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7817
  • 题目
  • P7817穴居人
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s 256MB
    问题描述

    两组穴居人发生了土地纠纷,决定用老办法解决,互相扔棍子。争斗是在一个山洞里发生的,山洞很高,所以天花板是不用担心的,但是地面上的矿藏却会妨碍飞来的棍子。

    洞可以分为 \(r\) 行和 \(c\) 列,所以整个洞口由 \(r \times c\) 个单元格组成(可当成一个竖直的平面)。

    洞穴中的每一个单元格要么是空的,要么含有一块矿物块。如果两块矿物在四个主要方向(上、下、左、右)中的一个方向相邻,则它们属于同一矿群。

    一组穴居人在山洞的左侧,另一组在右侧。这两组人轮流向另一组人投掷棍子,先由一组人选择棍子飞行的高度,然后(必要时爬到别人的肩膀上)投掷,棍子在选定的高度水平飞过洞穴。

    如果棍子在路上撞到了一块矿块,就会破坏矿块,单元格变成空的,棍子也就停止了行程。

    当一个块状物被破坏时,有可能会有一个集群散落下来。如果一个新创建的集群会漂浮在空中,那么它就会因为重力而坠落。在下落的过程中,集群不会改变形状,即其中所有的块都会一起下落。只要下降的途中的某个块落在另一个集群的块上或地面上,整个集群就会停止下降。当然,如果一个集群落在另一个集群上,它们就会合并成为一个集群。

    已知洞穴中矿物的布局和扔棍子的高度。确定棒子扔完后的矿物布局。

    输入格式

    第一行,两个整数 \(r\), \(c\),含义见题目描述。

    接下来,\(r\)\(c\) 列。 . 代表一个空单元格,x 代表一块矿物质。

    接下来,一个正整数 \(n\),表示木棍个数。

    最后一行,\(n\) 个整数,表示棍棒的投掷高度。高度 $1$ 为矩阵的底部,高度 \(r\) 为顶部。 第一根棍从左向右扔,第二根从右向左,以此类推。

    最初不会有任何一个集群漂浮在空中。另外,输入的数据将是这样的:在任何时候都不会有两个或两个以上的集群同时落下,所以不会出现模棱两可的情况。

    $1 ≤ r,c,n ≤ 100$。

    输出格式

    输出由 \(r\) 行组成,每行 \(c\) 个字符,表示洞穴的最终布局。

    样例输入 1

    5 6
    ......
    ..xx..
    ..x...
    ..xx..
    .xxxx.
    1

    样例输出 1

    ......
    ......
    ..xx..
    ..xx..
    .xxxx. 

    样例输入 2

    8 8
    ........
    ........
    ...x.xx.
    ...xxx..
    ..xxx...
    ..x.xxx.
    ..x...x.
    .xxx..x.
    5
    6 6 4 3 1 

    样例输出 2

    ........
    ........
    ........
    ........
    .....x..
    ..xxxx..
    ..xxx.x.
    ..xxxxx. 

    样例输入 3

    7 6
    ......
    ......
    xx....
    .xx...
    ..xx..
    ...xx.
    ....x.
    2
    6 4 

    样例输出 3

    ......
    ......
    ......
    ......
    ..xx..
    xx.xx.
    .x..x.