小明有一张矩形彩纸,他将彩纸均匀的画了N*M个小方格,有些小方格中被他画了小草,有些小方格是空白的,现小明想找出一片空白的方格,并且这片空白方格是最大的矩形。
现给出N和M的值,及每个方格的状态,被画小草的小方格用数字1表示,空白小方格用数字0表示,请帮小明找出最大矩形,并输出最大矩形由多少个小方格组成。
例如:N=4,M=5,矩阵如下: | 1 | 1 | 0 | 0 | 0 | |----|----|----|----|----| | 1 | 0 | 1 | 0 | 0 | | 0 | 0 | 0 | 1 | 1 | | 0 | 0 | 0 | 1 | 0 | 其中左侧2行3列的全0区域即为最大矩形,共6个方格。
第一行输入两个正整数N和M(2≤N≤100,2≤M≤100),分别表示矩形彩纸方格的行数和列数,两个正整数之间以一个空格隔开。
第二行开始,输入N行,每行M个正整数(正整数为1或者0),1表示小草,0表示空白,正整数之间一个空格隔开。
输出一个整数,表示最大矩形由多少个小方格组成。
4 5
1 1 0 0 0
1 0 1 0 0
0 0 0 1 1
0 0 0 1 0
6
| 输入 | 输出 |
|---|---|
| 2 2<br>1 0<br>1 0 | 1 |
| 3 6<br>1 0 1 0 1 0<br>0 1 0 0 0 1<br>1 0 1 0 1 0 | 3 |
| 4 5<br>1 0 1 0 0<br>1 0 1 1 1<br>1 1 1 1 1<br>1 0 0 1 0 | 6 |
| 7 10<br>1 0 1 1 1 0 1 1 1 1<br>1 1 0 1 1 1 0 1 1 1<br>1 0 1 1 0 1 1 1 1 1<br>1 0 0 1 1 0 0 0 1 0<br>1 1 0 1 0 0 1 0 1 0<br>0 1 0 0 0 1 0 1 1 0<br>1 1 0 1 0 0 1 0 1 0 | 4 |
| 7 10<br>1 0 1 1 0 1 0 1 0 1 1 0 1<br>1 1 0 1 0 1 1 0 1 1 0 1 1<br>1 0 1 1 0 1 1 1 1 1 0 0 1<br>1 0 0 1 1 0 0 0 0 0 1 1 0<br>1 0 0 1 1 0 0 0 0 1 0 1 0<br>0 0 1 0 1 0 0 0 1 0 1 1 0<br>1 0 0 1 1 0 1 0 0 1 0 1 0<br>1 1 1 1 0 1 1 0 1 0 1 0 0<br>1 0 1 0 1 0 1 0 1 1 1 0 1 | 9 |