#LQ1024. 最大空白区

最大空白区

题目描述:

小明有一张N×MN×M的方格纸,且部分小方格中涂了颜色,部分小方格还是空白。

给出NNMM的值,及每个小方格的状态(被涂了颜色小方格用数字11表示,空白小方格用数字00表示),请帮助小明找出最大的矩形空白区域,并输出该矩形空白区域由多少个小方格组成。

例如:N=4M=5N=4,M=54×54×5的方格纸中每个小方格的状态如下图:

a.png

最大的空白区域由6个小方格组成(红色框区域)。

输入描述

第一行输入两个正整数NNMM,分别表示方格纸的行数和列数,两个正整数之间以一个空格隔开

第二行开始输入NN行,每行MM个整数(整数为1或者0),1表示涂色方格,0表示空白方格,整数之间以一个空格隔开

输出描述

输出一个整数,表示最大矩形由多少个小方格组成(如果没有空白小方格,输出0)

样例输入

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

样例输出

6

提示

2N302M30(2≤N≤30,2≤M≤30)