题目描述
小猴最近在玩一款非常火热的游戏
“巨石滚滚”,游戏中某一个关卡难住了小猴。具体来说,该关卡
给定一个 $n×m$ 的矩阵,矩阵中包含三种类型的单元格:
- 空单元格,用 $.$ 表示;
- 一块巨石,用 $*$ 表示;
- 一个障碍物,用 # 表示。
游戏开始时,所有巨石都会掉落下来(第一行最高,第 $n$ 行最低)直到碰到地板(第 $n$ 行)、障碍物或其他已经无法移动的巨石才会停止掉落。
现在给定矩阵中每个单元格的初始状态,即每个单元格可能为空、有一块巨石或有一个障碍物,请你帮助小猴计算矩阵中所有单元格的最终状态。
【输入格式】
第一行,两个整数 $n,m$;
接下来 $n$ 行,每行包含 $m$ 个字符,每个字符都是$.$,$*$,# 三者之一。
【输出格式】
$n$ 行,每行包含 $m$ 个字符,每个字符都是$.$,$*$,# 三者之一,表示矩阵的最终状态。
【输入输出样例#1】
输入#1
5 5
*****
*....
*****
....*
*****
输出#1
.....
*...*
*****
*****
*****
【输入输出样例#2】
输入#2
2 9
...***###
.*#.*#.*#
输出#2
....**###
.*#**#.*#
【输入输出样例#3】
输入#3
6 10
.*.*....*.
.*.......*
...#....#.
.*.*....*.
..........
.#......#*
输出#3
..........
...*....*.
.*.#....#.
.*........
.*......**
.#.*....#*
【数据范围】
对于 $100\%$ 的数据:
$1≤n,m≤2000$。
解题思路
- 首先记录下来每个障碍物的位置和每列障碍物的个数,并且把每一列的 $n + 1$ 行也设置成障碍物,以防石头下面没有障碍物,无法落下
- 然后用双重循环遍历石头的位置,再找到该石头落到的障碍物(地板)的位置,把障碍物-1的位置和石头的位置交换,并且把障碍物的行坐标-1,因为石头也占地方
C++ 代码
#include <iostream>
using namespace std;
char c[2005][2005]; // 初始地图
int p[2005][2005], cur[2005];
// p[x][y] = z 表示第x列从上往下数第y个障碍物在第z行
// cur[x] 表示第x列有几个障碍物
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) { // 读入初始地图
for (int j = 1; j <= m; j++) {
cin >> c[i][j];
}
}
for (int j = 1; j <= m; j++) { // 遍历列
int cc = 0; // 第j列的障碍物总数
for (int i = 1; i <= n; i++) { // 遍历行
// 如果是障碍物,就记录位置,和更新个数
if (c[i][j] == '#') {
p[j][++cc] = i;
}
}
p[j][++cc] = n + 1; // 把地板也算作障碍物
cur[j] = cc; // 存储当前列的障碍物的个数
}
for (int j = 1; j <= m; j++) { // 遍历列 从上往下
for (int i = n; i >= 1; i--) { // 遍历行 从下往上
if (c[i][j] == '*') { // 如果是石头
// 找到石头会落到的障碍物的位置,和石头的位置交换,再把石头也算作障碍物
for (int k = 1; k <= cur[j]; k++) {
if (p[j][k] > i) {
swap(c[--p[j][k]][j], c[i][j]);
break;
}
}
}
}
}
for (int i = 1; i <= n; i++) { //输出结果
for (int j = 1; j <= m; j++) {
cout << c[i][j];
}
cout << endl;
}
return 0;
}