题目大意

给定一个 $N \times M$ 的网格，每个格子是空地（.）或石头（#）。边界都是石头。定义第 $i$ 行的高度为 $N+1-i$（从上到下高度递减）。

要将一些空地染成水，满足以下约束：如果格子 $a$ 是水，那么所有从 $a$ 出发，通过高度不超过 $a$ 的空地或水格子能到达的格子 $b$ 也必须是水。

求不同的染色方案数，模 $10^9+7$。

问题分析

关键约束理解

水流动规则：水只能往高度相等或更低的连通区域流动，且一旦某个区域有水，所有与其连通且高度不超过该区域的区域都必须有水。

这实际上定义了一个偏序关系：水只能从高往低流，且连通区域内的水必须保持一致。

问题转化

可以将问题转化为：

1. 识别连通区域：在高度约束下的连通分量
2. 建立依赖关系：高处的连通区域会影响低处的连通区域
3. 组合计数：在依赖关系下计算所有合法的染色方案

算法设计

方法一：自底向上的并查集 + 树形DP

核心思想： 从底部（高度最低）开始向上处理，逐行合并连通区域，并计算每个连通区域的方案数。

具体步骤：

1. 初始化：

   • 为每个空地格子创建独立的连通分量
   • 每个连通分量初始方案数为 2（有水/无水）

2. 自底向上处理：

   • 从最后一行（高度为1）开始，向上处理到第一行
   • 对于每一行，先处理行内的连通性，再处理与下一行的连通性

3. 连通分量合并：

   • 当两个连通分量合并时，新的方案数 = 原方案数之积 + 1
   • 解释：两个区域可以独立选择，但也可以选择都不染色（+1 表示全无水的方案）

4. 最终计算：

   • 所有独立的连通分量的方案数相乘

伪代码：

for i from N-1 down to 1:  # 从底部向上
    for j from 1 to M-1:
        if grid[i][j] == '.':
            # 处理行内连通性
            if grid[i][j-1] == '.':
                union((i,j), (i,j-1))
    
    # 处理与下一行的连通性  
    for j from 1 to M-1:
        if grid[i][j] == '.' and grid[i+1][j] == '.':
            union((i,j), (i+1,j))
    
    # 更新方案数
    for 每个连通分量:
        if 该分量包含当前行的格子:
            方案数 = (所有子分量方案数乘积) + 1

方法二：分量树构建 + 组合计数

核心思想： 构建一个分量树，其中父节点表示会影响子节点水状态的高处区域。

具体步骤：

1. 构建分量图：

   • 扫描网格，识别所有连通区域（考虑高度约束）
   • 建立区域之间的依赖关系（高处区域影响低处区域）

2. 构建分量树：

   • 每个连通区域作为一个节点
   • 如果区域 A 的水会影响区域 B，则 A 是 B 的祖先

3. 树形DP计数：

   • 对于每个节点，方案数 = (所有子节点方案数乘积) + 1
   • +1 表示该节点及其所有后代都不染水的方案

实现细节

并查集优化

• 路径压缩：加速查找操作
• 按秩合并：保持树结构的平衡
• 方案数维护：在合并时正确更新方案数

边界处理

• 石头格子不参与连通性计算
• 边界都是石头，确保不会越界
• 高度比较时注意等高的处理

模运算处理

所有乘法操作都要对 $10^9+7$ 取模：

const int MOD = 1e9 + 7;
方案数 = (方案数1 * 方案数2 + 1) % MOD;

复杂度分析

• 时间复杂度：$O(NM \cdot \alpha(NM))$，其中 $\alpha$ 是反阿克曼函数
• 空间复杂度：$O(NM)$

关键洞察

1. 自底向上处理：水往低处流，所以从低处开始处理可以自然建立依赖关系
2. 方案数递推：合并两个区域时，新方案数 = 原方案数积 + 1
3. 物理约束建模：将水流动的物理约束转化为图论中的连通性约束

特殊情况

1. 孤立区域：不影响其他区域，方案数为 2
2. 完全连通：所有区域必须同时有水或无水，方案数为 2
3. 链式依赖：形成链状依赖关系，方案数呈斐波那契数列增长

总结

本题的核心在于将物理世界中的水流动约束转化为图论中的连通性问题和组合计数问题。通过自底向上的处理顺序和并查集数据结构，可以高效地计算满足所有约束的染色方案数。

算法选择建议：方法一（自底向上并查集）实现相对简单，且时间复杂度优秀，是解决此类问题的经典方法。