注意此题和一维的版本不一样,无法使用DP的思想。
我们将矩阵所有的边界格子加入一个优先队列,里面的格子按照海拔从低到高排列。这些边界格子相当于闭合的堤岸,围了中间的区域。
我们想象一下海平面逐渐上涨的过程,当海平面cur上涨到优先队列里最矮的那个元素时,就相当于从那里冲破了堤岸,拓展进了内陆、同时会有新的堤岸格子加入队列。如果加入队列的这一系列新格子高度都小于cur,那么它们其实也被淹没了,洪水可以基于它们的位置继续向四周扩展。这个“泛滥”的过程直到队列里面的所有元素高度(也就是首元素)都大于cur为止。在上面的过程中,所有被“淹没”的格子(i,j),计算cur-h(i,j)
就是该点的储水量。
然后重复上述的过程,再次想象海平面cur上涨到队列最矮元素的高度,这样就再一次“决堤”,这个泛滥的过程依然是在各地“储水”的机会,直至队列里面的堤岸都高于海平面cur位置,“泛滥”结束。
以上过程中,所有被“决堤”或者被“淹没”的格子,都要做标记,不用重复入队列。直至队列为空停止。