解题思路

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

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

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

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

题目内容

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

矩阵范围之外为海拔为 $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$

示例图: