1134 . 1.蓋房子問題
TopCoder
Tags
Description
在一塊大小為M*N單位方格的土地上，每一個單位格子可能適合(標記為0)，或不適合(標記為1)用於建築。
對於某個矩形範圍X，若範圍X裡面適合建築的格子數比不適合建築的格子數多，我們就說個矩形範圍X適合蓋房子。
請問最大能蓋多大面積的房子呢？
Input Format
輸入的第一列有一個正整數T(1<=T<=20)代表接下來測試資料的組數。
每筆測試資料的第一列有兩個正整數N,M(1<=N,M<=200)代表地圖的長寬，
然後有N列每列M個以空白隔開的0或1代表這格適合，或不適合用來蓋房子。
Output Format
對於每筆測試資料請輸出一個整數代表最大可建築面積。
Sample Input 1
1
5 5
0 1 0 0 1
1 0 1 1 1
0 0 1 1 0
0 1 1 0 1
1 1 0 1 0
5 5
0 1 0 0 1
1 0 1 1 1
0 0 1 1 0
0 1 1 0 1
1 1 0 1 0
Sample Output 1
9
Hints
在上面的範例中，左上角3*3的範圍是最大適合蓋房子的區域。
※最大的測試資料(i.e. 200*200大小的地圖)只有兩筆。
Problem Source
原TIOJ1134 / 96 TWN Practice Contest 1。Problem Setter: Tmt。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 33 |
| 2 | 1 | 33 |
| 3 | 2 | 34 |