#8. 巨石滚滚

巨石滚滚

说明

小珅最近在一款非常火热的游戏“巨石滚滚”,游戏中某一个关卡难住了小珅。具体来说,该关卡
给定一个 <math xmlns="http://www.w3.org/1998/Math/MathML">n×m 的矩阵,矩阵中包含三种类型的单元格:
  • 空单元格,用 . 表示;
  • 一块巨石,用 * 表示;
  • 一个障碍物,用 # 表示。
游戏开始时,所有巨石都会掉落下来(第一行最高,第 <math xmlns="http://www.w3.org/1998/Math/MathML">n 行最低),直到碰到地板(第 <math xmlns="http://www.w3.org/1998/Math/MathML">n 行)、障碍物或其他已经无法移动的巨石才会停止掉落。
现在给定矩阵中每个单元格的初始状态,即每个单元格可能为空、有一块巨石或有一个障碍物,请你帮助小珅计算矩阵中所有单元格的最终状态。

输入格式

第一行,两个整数 <math xmlns="http://www.w3.org/1998/Math/MathML">n,m

接下来 <math xmlns="http://www.w3.org/1998/Math/MathML">n 行,每行包含 <math xmlns="http://www.w3.org/1998/Math/MathML">m 个字符,每个字符都是 <math xmlns="http://www.w3.org/1998/Math/MathML">.<math xmlns="http://www.w3.org/1998/Math/MathML"><math xmlns="http://www.w3.org/1998/Math/MathML"># 三者之一。

输出格式

n 行,每行包含 <math xmlns="http://www.w3.org/1998/Math/MathML">m 个字符,每个字符都是 <math xmlns="http://www.w3.org/1998/Math/MathML">.<math xmlns="http://www.w3.org/1998/Math/MathML"><math xmlns="http://www.w3.org/1998/Math/MathML"># 三者之一,表示矩阵的最终状态。
5 5
*****
*....
*****
....*
*****
.....
*...*
*****
*****
*****

提示

对于 <math xmlns="http://www.w3.org/1998/Math/MathML">100% 的数据:<math xmlns="http://www.w3.org/1998/Math/MathML">1n,m2000

来源

模拟