7899 - 试题J:最大蓄水量 25'

JM小学购买了一块n*m大小矩形土地A,学校准备用这块土地来蓄水,以备不时之需。但是JM小学花了天价购买了这块矩形土地,已无资金去开垦这片土地。所以,目前只能利用已有地形蓄水。

现在已知这n*m个小正方形块的高度,JM趁着天降大水,利用这块土地蓄水。由于高度不一,当某水块相邻四个方向的正方形块高度不高于该正方形块时,则该水块的水流可以流向相邻不高于该水块的位置。

假设水平面高度为0,即A土地边缘外均为高度为0土地。

输入

第一行包含两个非负整数n,m。 

接下来n行每行m个整数表示第i行第j列的小正方形块的高度。

输出

输出n行,每行m个由空格隔开的非负整数,表示每个小正方形块的积水高度。 

样例

输入

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

输出

0 0 0
0 1 0
0 0 1

输入

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

输出

0 0 0 0 0
5 4 5 5 5
0 0 1 0 0

提示

样例1解释

5 5                                   0

2 1(可以蓄1高度的水)     6

4 5                                   -1(可以蓄1高度的水)

15892146399093.png

数据规模

对于 20\%的数据 n,m<=4 

对于 40\%的数据 n,m<=15 

对于 60\%的数据 n,m<=50 

对于 100\%的数据 n,m<=300,|小正方形块高度|<=10^9。 

来源

竞码编程-蓝桥杯模拟赛6(大学生组&青少年组)
时间限制 1 秒
内存限制 256 MB
讨论 统计
上一题 下一题