[R40C]Yet another gravity problem - 代码源竞赛平台

时空限制

1S/512M

在一个物流仓库中，机械臂突然发生故障，导致所有悬挂在空中的货物箱子同时垂直掉落。

仓库场景可以用一个 $n \times m$ 的网格表示，每个格子包含以下三种字符之一：

所有箱子同时垂直下落，直到遇到以下情况之一才会停止：

每个箱子从初始位置 $(r_{start}, c)$ 下落到静止位置 $(r_{end}, c)$ ，定义其下落距离 $d = r_{end} - r_{start}$ 。

每个箱子都有一个耐摔程度 $k$ ：

注意：废墟 * 仍然占据该格子，可以支撑落在上方的物体。

请你输出所有箱子下落后的最终网格。

第一行包含三个整数 $n, m, k$ ，分别表示网格的行数、列数和箱子的耐摔程度。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，表示掉落前的初始状态。字符集为 .、- 和 A-Z。

输出 $n$ 行，每行 $m$ 个字符，表示掉落并结算后的最终状态。

4 2 1
A.
..
.B
-.

..
..
*.
-B

对于箱子 A：箱子 A 原本在第 1 行，掉落到第 3 行（停在 - 上方）。此时下落距离 $d = 3 - 1 = 2$ 。因为 $2 > k$ ，A 被摔碎，最终在第 $3$ 行显示为 *。

对于箱子 B：箱子 B 原本在第 3 行。下方无障碍，直接掉落至第 4 行（网格底部）。此时下落距离 $d = 4 - 3 = 1$ 。因为 $1 \le k$ ，B 完好，最终在第 $4$ 行显示为 B。

对于 $30\%$ 的数据， $1 \leq n, m \le 100$ 。

对于 $100\%$ 的数据， $1 \le n, m \le 1000$ ， $0 \le K < n$ 。