解题思路

• 本题题面给出矩阵外的海平面高度为 0。

• 关键想法：从外到内逐层“抬高”水位。把能和外界连通的最低挡水高度维护在一个最小堆里，始终从当前最低的“边界”向内扩展。

• 具体算法（最小堆 + BFS）

  1. 建一个最小堆，初始把四周边界格入堆，但其有效高度取 max(原高度, 0)（因为外侧是海平面 0）。 同时，边界上若高度为负，需要先补到 0，因此将 -height 加到答案（这些格与海相邻，直接被海水填平到 0）。

  2. 弹出堆顶 (h, x, y)，向四邻扩展：

     • 若邻格高度 nh < h，则该邻格可蓄水 h - nh，并把它的有效高度提升为 h；
     • 将邻格以 max(nh, h) 压入堆。

  3. 直到堆空，累加值即为总蓄水量。

• 正确性：最小堆保证每次以当前可达最低的边界水位推进，等价于从外海（高度 0）向内涨水，不会遗漏或重复计算。

复杂度分析

• 设矩阵大小为 N × M（题面 N, M ≤ 300）。
• 每个格子最多进堆一次，堆操作 log(NM)，故时间复杂度为 O(NM log(NM))。
• 需要一个访问标记矩阵与堆，空间复杂度为 O(NM)。
• 在数据范围内完全可行。

代码实现

Python

# ACM 风格：主函数处理输入输出，核心逻辑写在函数里
import sys
import heapq

def total_water(m, n, a):
    # m: 列数(宽), n: 行数(高)
    if m == 0 or n == 0:
        return 0
    visited = [[False] * m for _ in range(n)]
    heap = []
    ans = 0

    # 1) 处理边界：海平面为0，边界负高先被填到0
    for i in range(n):
        for j in range(m):
            if i == 0 or i == n - 1 or j == 0 or j == m - 1:
                h = a[i][j]
                if h < 0:
                    ans += -h  # 被海水直接填到0
                eff = h if h > 0 else 0  # 有效高度与海平面取max
                heap.append((eff, i, j))
                visited[i][j] = True
    heapq.heapify(heap)

    # 2) 从外向内，用最小堆逐层抬高水位
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while heap:
        h, x, y = heapq.heappop(heap)
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                nh = a[nx][ny]
                if h > nh:
                    ans += h - nh      # 可蓄水
                    nh = h             # 抬到边界水位
                visited[nx][ny] = True
                heapq.heappush(heap, (nh, nx, ny))
    return ans

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    m, n = data[0], data[1]  # 题面：先宽M再高N
    a = []
    idx = 2
    for _ in range(n):
        row = data[idx:idx + m]
        idx += m
        a.append(row)
    print(total_water(m, n, a))

if __name__ == "__main__":
    main()

Java

// ACM 风格：类名 Main，主函数读写，核心逻辑在静态函数里
import java.io.*;
import java.util.*;

public class Main {
    static long solve(int m, int n, int[][] a) {
        boolean[][] vis = new boolean[n][m];
        // 小根堆：[高度, x, y]
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[0]));
        long ans = 0;

        // 1) 边界入堆（与海平面0比较），边界负高先被海水填平
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                    int h = a[i][j];
                    if (h < 0) ans += -(long)h;
                    int eff = Math.max(h, 0);
                    pq.offer(new int[]{eff, i, j});
                    vis[i][j] = true;
                }
            }
        }

        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        // 2) 从外向内扩展
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int h = cur[0], x = cur[1], y = cur[2];
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k], ny = y + dy[k];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny]) {
                    int nh = a[nx][ny];
                    if (h > nh) {
                        ans += (long)h - nh; // 蓄水量
                        nh = h;              // 抬到水位线
                    }
                    vis[nx][ny] = true;
                    pq.offer(new int[]{nh, nx, ny});
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {
        // 根据范围，BufferedReader + StringTokenizer 足够
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken()); // 宽
        int n = Integer.parseInt(st.nextToken()); // 高
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(solve(m, n, a));
    }
}

C++

// C++11 兼容版：不使用结构化绑定/tuple
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Node {
    int h, x, y;
};
struct Cmp {
    bool operator()(const Node& a, const Node& b) const {
        return a.h > b.h; // 小根堆：高度小的优先
    }
};

long long solve(int m, int n, const vector<vector<int>>& a) {
    if (m == 0 || n == 0) return 0;
    vector<vector<int>> vis(n, vector<int>(m, 0));
    priority_queue<Node, vector<Node>, Cmp> pq;
    long long ans = 0;

    // 边界入堆（海平面为0），边界负高先被海水填到0
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                int h = a[i][j];
                if (h < 0) ans += -(long long)h;
                int eff = h > 0 ? h : 0;
                pq.push(Node{eff, i, j});
                vis[i][j] = 1;
            }
        }
    }

    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    // 从外向内扩展
    while (!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        int h = cur.h, x = cur.x, y = cur.y;
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny]) {
                int nh = a[nx][ny];
                if (h > nh) {
                    ans += (long long)h - nh; // 蓄水
                    nh = h;                   // 抬到水位线
                }
                vis[nx][ny] = 1;
                pq.push(Node{nh, nx, ny});
            }
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n; // 先宽M，再高N
    if (!(cin >> m >> n)) return 0;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> a[i][j];

    cout << solve(m, n, a) << "\n";
    return 0;
}

题目内容

给定一个表示地图的矩阵，其中元素表示地形海拔高度。当一个地形块在水平和垂直方向均被海拔高度更高的地形包围时，该地形即可蓄水。

矩阵范围之外为海拔为 $0$，无法蓄水。

要求计算整块地图的蓄水量

输入描述

第 $1$ 行:$M$ $N$

$M$ 是矩阵的宽，范围是 $[1,300]$

$N$ 是矩阵的高，范围是 $[1,300]$

第 $2$ 到第 $N+1$ 行:$X_1X_2…X_M$,为矩阵第一行，每个元素的范围是 $[-500,8000]$

输出描述

输出 $1$ 个数字，表示地图中的中蓄水量。每个地块面积为 $1$ ，累加所有可蓄水地块的可蓄水的高度

样例1

输入

1 1
-10

输出

10

说明

第 $1$ 行 $1$ $1$ 表示该矩阵长宽均为 $1$

仅有一块海波为 $-10$ 的地形，蓄水量为 $10*1=10$

样例2

输入

2 2
-500 -500
-500 -500

输出

2000

说明

第 $1$ 行 $2$ $2$ 表示矩阵宽和高均为 $2$

第 $2$ 到 $3$ 行表示矩阵为

$-500$ $-500$

$-500$ $-500$

则每块地的海拔为 $-500$ ，在地形上看出一个深度为 $500$ 的湖，蓄水量为 $500*4=2000$

样例3

输入

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

输出

11

说明

第 $1$ 行 $4$ $5$ 表示矩阵的宽为 $4$ ，高为 $5$

矩阵中如下位置可以蓄水的地块中有 $3$ 块海拔为 $-1$，$1$ 块海拔为 $0$ 。周围海拔最低处为 $2$ ，所以有 $3$ 个地块可以蓄水 $3,1$ 个地块蓄水 $2$ 。因此蓄水量为 $3+3+3+2=11$

$0$ $2$ $3$ $4$

$2$ -1 -1 $4$

$2$ 0 -1 $3$

$4$ $4$ $4$ $4$

$4$ $0$ $0$ $1$

样例4

输入

4 4
0 2 3 4
2 0 0 4
2 0 0 3
4 4 4 4

输出

8

说明

第一行 $4$ $4$ 表示矩阵的宽和高均为 $4$

矩阵中如下位置可以蓄水的面积为 $4$ 海拔为 $0$ ，周围海拔最低处为 $2$ ，因此蓄水量为 $4*2=8$

$0$ $2$ $3$ $4$

$2$ 0 0 $4$

$2$ 0 0 $3$

$4$ $4$ $4$ $4$

示例图: