题目理解

我们有一个 $N \times M$ 的网格，其中 # 表示方块，. 表示空格。水平或垂直相邻的方块属于同一个物体。所有物体同时向下掉落，直到：

碰到网格底部，或者

碰到下方的其他物体## 关键观察 物体识别：使用 Flood Fill 或并查集找出所有连通块（物体）

下落距离计算：对于每个物体，计算它能下落的最大距离

最终位置确定：根据下落距离重新放置物体

算法步骤

步骤 1：识别物体（连通块） 遍历整个网格，对每个未访问的 # 进行 BFS/DFS

记录每个连通块包含的所有坐标

为每个连通块分配唯一 ID

步骤 2：计算每个物体的下落距离 对于每个连通块：

找出块中每个列的最低方块位置

对于每列，计算从该列最低方块到下方障碍物的距离

整个物体的下落距离 = 所有列下落距离的最小值

步骤 3：重新构建最终网格 创建空的结果网格（全为 .）

对于每个连通块，将其所有方块向下移动计算出的下落距离

在结果网格的对应位置放置 #

时间复杂度

识别连通块：$O(N \times M)$

计算下落距离：$O(N \times M)$

总体复杂度：$O(N \times M)$，满足 $N \times M \leq 10^6$ 的要求

优化技巧

预处理列信息：预先计算每列从每个位置向下的空格数，避免重复计算

批量处理：对每个连通块整体计算下落距离，而不是逐个方块计算

内存优化：使用原地标记或压缩存储来减少内存使用