logo AlgoBeat OnlineJudge
登录 注册

#214349. [语言月赛 202510] 下落模拟

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

现有一面墙,可以看作 列的网格,其中从上往下第 行、从左到右第 列的格子记为

每个格子可能有一个箱子、一块挡板,或者没有东西。箱子有 种(未必只有 个),用大写字母标号。

具体地,我们使用一个字符数组 来表示这个网格,其中:

  • 是大写字母时表示 是一个标号为 的箱子。
  • 是减号 - 时表示 是一块挡板。
  • 是句点 . 时表示 没有东西。

由于重力原因,在任意时刻,如果一个在 的箱子下方格子(即 存在并且没有东西,那么它会下落到这个格子。

给出初始时每个格子上的情况,输出经过足够长的时间后每个格子的情况。

输入格式

第一行有两个正整数 ,表示网格的行数和列数。

之后有 行,每行有一个长为 的字符串,表示这个网格 ,具体含义同题目描述。

输出格式

输出 行,每行有一个长为 的字符串,表示足够长的时间之后的网格,输出格式同题目描述。

样例

样例输入 1

6 3
A.B
...
..-
..D
C..
...

样例输出 1

...
..B
..-
...
A..
C.D

数据范围与提示

【数据范围】

对于全部数据,保证 只可能是 .- 或大写字母。

本题共有 个测试点,部分测试点有特殊限制,具体如下:

测试点编号 特殊性质
1,2
1
2
1,2
1
2

其中:

  • 特殊性质 1:保证没有挡板。
  • 特殊性质 2:保证箱子只有 A

提示:从下往上依次考虑每一个箱子的最终位置,就可以保证每个箱子落地后一定不再移动。