填寫問券˙抽7-11禮券來自星星的你也會打廣告?法人:14檔今年本業虧定了黃曉明、林志玲攜手代言...
2012-02-26 11:19:24 人氣(504) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA] 836 - Largest Submatrix

0
收藏
0
推薦

  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 $ le$ N $ le$ 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;
}

836Largest Submatrix
台長:Morris
人氣(504) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 10074 - Take the Land
此分類上一篇:[UVA][JAVA][BigNumber] 787 - Maximum Sub-sequence Product

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文