Largest Submatrix

Let A be an N×N matrix of zeros and ones. A submatrix S of A is any group of contiguous entries that forms a square or a rectangle.

Write a program that determines the number of elements of the largest submatrix of ones in A. Largest here is measured by area.

Input 

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The matrix is given line by line. Each line consists of 0's and 1's. The order of the matrix is also the number of lines input and 1 N 25.

Output 

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

The output is the number of elements of the largest submatrix found.

Sample Input 

1

10111000
00010100
00111000
00111010
00111111
01011110
01011110
00011110

Sample Output 

16

---

做法 : DP 解
時間複雜度 O(N^3)

#include <stdio.h>
#include <string.h>

int main() {
	int T;
	int i, j, k;
	char clear[3], map[50][50];
	scanf("%d", &T);
	gets(clear);
	while(T--) {
		gets(clear);
		gets(map[0]);
		int row, column;
		row = column = strlen(map[0]);
		for(i = 1; i < row; i++)		
			gets(map[i]);
		int max = 0, length, width, tmp;
		for(i = 0; i < row; i++) {
			int sum[50] = {};
			for(j = i; j < row; j++) {
				for(k = 0; k < column; k++) {
					sum[k] += map[j][k]-'0';
					if(k == 0 || tmp != length*width)
						tmp = 0, length = 0;
					tmp += sum[k];
					length++, width = j-i+1;
					if(tmp == length*width)
						max = max > tmp ? max : tmp;
				}
			}
		}
		printf("%d\n", max);
		if(T)	puts("");
	}
    return 0;
}