原创水题：重力井

本系列为原创垃圾水题，供学校新生天梯赛等算法竞赛以及博君一笑之用。

与其说是算法题，不如说是以模拟为主的思维题。

题目描述

在早期版本的 Minecraft 手机版（即 Pocket Edition）中，没有红石系统。

但是当时已经有一些简单的机关，其中之一的实现方式是在仙人掌等易被破坏的方块上放置一些相互堆叠的告示牌，并在这些告示牌的最顶层放置一些受重力影响、会掉落的方块（比如沙子或者沙砾）。

当受重力影响的方块检测到自身的位置不合理时，就会移除自身并生成一个下落的方块，持续向下下落，直到接触到任意可站立表面。

落地后，如果下落的方块所在位置（碰撞箱底面中心的坐标）的方块是空气，那么这个方块就会在落地位置变成方块。

而告示牌、火把、草等方块虽然不直接受重力影响，但当其所附着的方块被破坏后，其自身也会变为掉落物（不会主动变回方块）。这些方块被统称为附着性方块。

此外，在 Minecraft 的一个世界存档生成时，可能生成一些悬空的、受重力影响的方块。这些方块在接收到一次方块更新时会开始检测自身状态。

现在 Steve 面前有一堆悬空的、受重力影响的方块，其中参杂了一些附着性方块。他希望知道这些方块落地后会是什么样子。

输入描述

多行输入。

第 $ 1 $ 行有 $ n $ 个非零数，$ a_1 \sim a_n $，每个不同的数字代表一种附着性方块。

第 $ 2 $ 行有一个非零数 $ m $，它表示悬空方块的层数。

第 $ 3 $ 行到第 $ 3+m $ 每行均有一些数字，每个数字代表一个方块。

这些方块中除了用 $ 0 $ 表示的空气，有且仅有附着性方块和受重力影响的方块。

输出描述

输出即这堆方块落地后的样子。

必要的空白区域用空气填充。

样例

• 输入数据 1

1 2
3
0 5 5 1 4 0 0
3 4 1 3 2 4 0
3 3 4 5 5 3 3

• 输出数据 1

0 5 0 0 0 0 0
3 4 5 3 4 4 0
3 3 4 5 5 3 3

• 输入数据 2

2 5 7 8
5
0 0 0 0 0 0 5 0
4 0 0 4 3 0 1 0
8 3 0 8 5 0 6 0
5 3 0 6 5 7 8 2
1 1 2 3 4 1 3 2

• 输出数据 2

0 3 0 4 0 0 1
4 3 0 6 3 0 6
1 1 0 3 4 1 3

提示

在本题目所考虑的任何情况下，最顶层、最左侧和最右侧至少有一个非空气方块。

掉落物不是方块。

样例解释

• 对于样例 1：

  • 落地前：
  • 落地后：

• 对于样例 2：

  • 落地前：
  • 落地后：

数据范围

• 除了层数 $ m $ 外，输入的任何一个数都在 $ [0,9] $ 的范围内。
• 你可以假定每层的方块数不超过 $ 100 $。

思路

首先创建一个数组或者集合来存储所有代表附着性方块的数字。

由于所有的附着性方块都会在落地过程开始后变成物品掉落，我们可以将所有代表附着性方块的数字都转变为代表空气的$ 0$。对于 C 和 C++ 而言，由于向二维数组中录入数字的过程是逐一进行的，可以在录入时就将匹配的数字录入为$ 0$；对于 Python 而言，在录入完成后遍历修改会更方便。

接下来的解题思路堪称暴力：

• 循环遍历二维数组，每次循环前保存二维数组状态；
• 只要当前方块的下方不是地面（当前数字所在的行数 $<$ 最大行数），就检测下方的方块是否为附着性方块或空气；
• 如果是，则将自己的位置下移（将原本的位置填充为空气）；
• 如果二维数组最左侧、最右侧或最顶部有一整列$ 0$，则去除整行或整列；
• 直到某一次循环后得到的数组和循环前的没有变化，跳出循环，打印结果。

题解

• Python

attached = set(map(int, input().split()))
grid = [list(map(int, input().split())) for _ in range(int(input()))]

while True:
    prev = [row[:] for row in grid]
    h, w = len(grid), len(grid[0])
  
    for y in range(h):
        for x in range(w):
            if grid[y][x] in attached:
                grid[y][x] = 0
            if grid[y][x] and y + 1 < h and (grid[y + 1][x] in attached or not grid[y + 1][x]):
                grid[y + 1][x], grid[y][x] = grid[y][x], 0
  
    if all(cell == 0 for cell in grid[0]):
        grid.pop(0)
  
    if sum(row[0] for row in grid) == 0:
        for row in grid:
            row.pop(0)
  
    if sum(row[-1] for row in grid) == 0:
        for row in grid:
            row.pop()
  
    if prev == grid:
        break

for row in grid:
    print(*row)

• C++

  本题的 C++ 题解经由 Python 题解由 Claude Sonnet 4.5 转写而来，仅保证逻辑基本一致，未做任何优化。

#include <iostream>
#include <vector>
#include <set>
#include <sstream>
using namespace std;

int main() {
    // 读取 attached 集合
    string line;
    getline(cin, line);
    set<int> attached;
    istringstream iss(line);
    int num;
    while (iss >> num) {
        attached.insert(num);
    }
  
    // 读取行数
    int n;
    cin >> n;
    cin.ignore();
  
    // 读取网格
    vector<vector<int>> grid(n);
    for (int i = 0; i < n; i++) {
        getline(cin, line);
        istringstream row_iss(line);
        int val;
        while (row_iss >> val) {
            grid[i].push_back(val);
        }
    }
  
    // 主循环
    while (true) {
        // 保存当前状态
        vector<vector<int>> prev = grid;
        int h = grid.size();
        int w = grid[0].size();
  
        // 处理 attached 和下落
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                if (attached.count(grid[y][x])) {
                    grid[y][x] = 0;
                }
                if (grid[y][x] != 0 && y + 1 < h && 
                    (attached.count(grid[y + 1][x]) || grid[y + 1][x] == 0)) {
                    swap(grid[y + 1][x], grid[y][x]);
                }
            }
        }
  
        // 删除首行（如果全为0）
        if (!grid.empty()) {
            bool all_zero = true;
            for (int x = 0; x < grid[0].size(); x++) {
                if (grid[0][x] != 0) {
                    all_zero = false;
                    break;
                }
            }
            if (all_zero) {
                grid.erase(grid.begin());
            }
        }
  
        // 删除首列（如果全为0）
        if (!grid.empty()) {
            int sum = 0;
            for (auto& row : grid) {
                sum += row[0];
            }
            if (sum == 0) {
                for (auto& row : grid) {
                    row.erase(row.begin());
                }
            }
        }
  
        // 删除末列（如果全为0）
        if (!grid.empty() && !grid[0].empty()) {
            int sum = 0;
            for (auto& row : grid) {
                sum += row.back();
            }
            if (sum == 0) {
                for (auto& row : grid) {
                    row.pop_back();
                }
            }
        }
  
        // 检查是否收敛
        if (prev == grid) {
            break;
        }
    }
  
    // 输出结果
    for (const auto& row : grid) {
        for (int i = 0; i < row.size(); i++) {
            if (i > 0) cout << " ";
            cout << row[i];
        }
        cout << endl;
    }
  
    return 0;
}