人类世界经历了旷日已久的干旱,雨师玄冥决定下一场雨来缓解人间的干旱。由于各种条件的限制,你只能用一种正方体砖在地平面上垒一个盛水的容器,等待雨师下雨时,用于积水。因为看起来像天坑,所以我们称为“找天坑”。
实际的情况更为糟糕,你能用的砖块已经被一个熊孩子以搭积木的形式搭在一个m行n列的矩形范围内。你现在需要做的是,在这m行n列的范围内,找到一个天坑,使得所盛的雨水体积最大。
砖头之间是无缝连接的.即只需要4块砖便可以垒出一个能盛放1体积雨水的天坑,如图所示。
第一行包含两个整数m和n,分别表示矩形区域砖块的行数和列数。
后面包括m行数据,每一行有n个非负整数,数字之间以空格相隔。每个数字表示该位置所放置的砖块高度(即堆放正方体砖块的数量)。
找出最大的那个天坑所能盛放雨水的体积。
3 3 0 1 0 1 0 1 0 1 0
1
3 3 1 1 1 1 0 1 1 1 0
1
3 6 1 6 1 0 1 1 1 0 0 1 0 0 1 5 0 4 1 1
0
对于100%的数据:n,m\leq 10^3
时间限制 | 2 秒 |
内存限制 | 128 MB |