问题分析

我们需要计算一个 $n \times m$ 的矩阵中每个位置能装水的最大高度。这个问题实际上是二维接雨水问题的变形。

关键观察：一个位置能装水的高度取决于从该位置到边界的所有路径中，路径上最大高度的最小值（木桶原理）。

算法思路

核心思想：边界传播算法

从矩阵的边界开始，使用优先队列（小根堆） 来维护当前的"水位边界"，确保总是从最低的边界点开始扩展。

算法步骤

1. 初始化：

   • 将所有边界点加入优先队列，并标记为已访问
   • 边界点的水位高度等于其原始高度

2. 主循环：

   • 从优先队列中取出高度最小的点
   • 使用 BFS 扩展所有高度小于等于当前水位的相邻点
   • 对于高度大于当前水位的点，加入优先队列

3. 水位确定：

   • 每个点的最终水位等于扩展到该点时当前边界的高度
   • 装水高度 = 最终水位 - 原始高度

代码详解

数据结构定义

struct bowl {
    int x, y, h;
    bool operator <(const bowl &k) const {
        return h > k.h;  // 小根堆
    }
};

初始化边界

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        scanf("%d", &high[i][j]);
        if (i == 1 || i == n || j == 1 || j == m) {
            vis[i][j] = true;
            q.push((bowl){i, j, high[i][j]});
        }
    }
}

核心算法

void work() {
    while (!q.empty()) {
        bowl k = q.top();      // 当前最低的边界点
        ableto.push(k);
        q.pop();
        water[k.x][k.y] = high[k.x][k.y];
        
        // BFS扩展所有水位以下的点
        while (!ableto.empty()) {
            bowl now = ableto.front();
            ableto.pop();
            water[now.x][now.y] = water[k.x][k.y];  // 设置水位
            
            // 四个方向扩展
            for (int i = 1; i <= 4; i++) {
                int tox = now.x + dx[i], toy = now.y + dy[i];
                if (tox < 1 || tox > n || toy < 1 || toy > m) continue;
                if (vis[tox][toy]) continue;
                
                vis[tox][toy] = true;
                if (high[tox][toy] <= water[now.x][now.y])
                    ableto.push((bowl){tox, toy, high[tox][toy]});  // 继续BFS
                else
                    q.push((bowl){tox, toy, high[tox][toy]});       // 加入优先队列
            }
        }
    }
}

木桶原理应用

• 边界点决定了水能装到的最低高度
• 通过总是从最低的边界开始扩展，确保内部点的水位不会超过从该点到边界的"瓶颈"高度

关键性质

1. 单调性：水位从边界向内部单调传播
2. 最优性：每次扩展都使用当前可能的最低水位
3. 完整性：所有点最终都会被处理到

复杂度分析

• 时间复杂度：$O(nm \log(nm))$
  • 每个点最多进入优先队列一次：$O(nm \log(nm))$
  • BFS扩展的总复杂度：$O(nm)$
• 空间复杂度：$O(nm)$
  • 存储高度矩阵、水位矩阵和访问标记
  • 优先队列和BFS队列的空间

算法优势

1. 高效性：利用优先队列确保最优扩展顺序
2. 正确性：基于物理原理的直观算法
3. 实用性：能够处理 $600 \times 600$ 规模的数据

总结

本题通过结合优先队列和BFS，实现了高效的二维接雨水算法。核心思想是利用木桶原理，从边界的最低点开始逐步确定内部点的水位高度。该算法在时间和空间复杂度上都达到了最优，能够处理题目要求的数据规模。

算法标签：优先队列BFS 二维接雨水 木桶原理 边界传播