2012-02-26 11:19:24Morris
[UVA] 836 - Largest Submatrix
Largest Submatrix
| 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;
}