water

water ( (starstar ))

• 时限：(1s) 内存：(256M)

Descrption

• 有一块矩形土地被划分成 (n*m) 个正方形小块。这些小块高低不平，每一小块都有自己的高度。水流可以由任意一块地流向周围四个方向的四块地中，但是不能直接流入对角相连的小块中。
• 一场大雨后，由于地势高低不同，许多地方都积存了不少降水。给定每个小块的高度，求每个小块的积水高度。
• 注意：假设矩形地外围无限大且高度为 (0)。

Input

• 第一行包含两个非负整数(n,m)。
• 接下来(n) 行每行(m) 个整数表示第(i) 行第(j) 列的小块的高度。

Output

• 输出 (n) 行，每行(m) 个由空格隔开的非负整数，表示每个小块的积水高度。

Sample Input

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

Sample Output

0 0 0
0 1 0
0 0 1

Hint

• 对于20%的数据 (n,m<=4)
• 对于40%的数据 (n,m<=15)
• 对于60%的数据 (n,m<=50)
• 对于100%的数据 (n,m<=300)，|小块高度|(<=10^9)。
• 在每一部分数据中，均有一半数据保证小块高度非负
• 来源：

分析

• 外围无限，且高度为 (0)，所以高度为负的至少能够装水到地平，首先能确定储水量的是矩形的四边上的点，对于其他的点就不好直接判断了，但根据水桶原理，能储多少水取决于最短的那块木板，所以我们可以把四边上的每一个点放到一个小根堆里，依次从高度最低的点往里搜，显然比他高的点是存不了水的，比他低的点可以存储他们高度差的水量，依次搜索即可。