每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m(1 <= n, m <= 75),表示田地的大小,接下来的 n 行,每行包含 m 个 0-9 之间的数字,表示每块位置的价值。
输出一行表示牛牛所能取得的最大的价值。
示例1
4 4
3332
3233
3332
2323
2
N, M = [int(each) for each in input().split()]
mat = [[int(each) for each in input().strip()] for i in range(N)]
left = min([min(each) for each in mat])
right = sum([sum(m) for m in mat]) // 16 + 1
sums = [[0 for j in range(M + 1)] for i in range(N + 1)]
for i in range(1, N + 1):
for j in range(1, M + 1):
sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + mat[i - 1][j - 1]
def sum_grid(x0, y0, x1, y1):
return sums[x1][y1] - sums[x0][y1] - sums[x1][y0] + sums[x0][y0]
def judge(mat, N, M, val):
for r1 in range(1, N - 2):
if sum_grid(0, 0, r1, M) < 4 * val: continue
for r2 in range(r1 + 1, N - 1):
if sum_grid(r1, 0, r2, M) < 4 * val: continue
for r3 in range(r2 + 1, N):
if sum_grid(r2, 0, r3, M) < 4 * val: continue
if sum_grid(r3, 0, N, M) < 4 * val: continue
start, count = 0, 0
for i in range(M + 1):
if sum_grid(0, start, r1, i) >= val \
and sum_grid(r1, start, r2, i) >= val \
and sum_grid(r2, start,r3,i) >= val \
and sum_grid(r3, start, N, i) >= val:
start, count = i, count + 1
if count == 4:
return True
return False
while left < right:
mid = (left + right) // 2
state = judge(mat, N, M, mid)
if state:
left = mid + 1
else:
right = mid
print(right - 1)