## 836 - Largest Submatrix

Moderator: Board moderators

miollnyr
New poster
Posts: 2
Joined: Mon Feb 08, 2010 8:44 pm

### Re: 836 Largest Submatrix

Can anybody take a look what is wrong with my code or provide some inputs?:)

Code: Select all

``````#include <iostream>
#include <vector>
#include <string>

using namespace std;

typedef vector<bool> line;
typedef vector<line> matrix;

int size = 0;

istream& operator>>(istream& in, line& L)
{
string str;
int i;

in >> str;

size = str.size();

for(i = 0; i < size; ++i)
{
L[i] = (str[i] == '1');
}

return in;
}

int func(const matrix& m)
{
int i, j, p, k, columns, ret = 0, curr;

for(i = 0; i < size; ++i)
{
for(j = 0; j < size; ++j)
{
if(m[i][j] && ret < (size - i)*(size - j))
{
curr = 0;
p = i;
k = j;
columns = size;

for(p = i; p < size && m[p][j]; ++p)
{
for(k = j ; k < columns && m[p][k]; ++k);

if(k < columns)
{
columns = k;
}
curr = max(curr, (p - i + 1) * (k - j));
}

ret = max(curr, ret);
}
}
}

return ret;
}

int main()
{
int num, i;
matrix m(25);

for(i = 0; i < 25; ++i)
{
m[i].resize(25);
}

cin >> num;

while(num--)
{
cin >> m;

for(i = 1; i < size; ++i)
{
cin >> m[i];
}

cout << func(m) << (num == 0 ? "" : "\n\n");
}

return 0;
}
``````
The idea is simple:
I start with cell with 1 and find the largest line with 1's - this is curr, size of line is columns
Then I start from the next line and find the largest line with ones with size <= columns (I am looking for rectangles), and curr = max(curr, size of new rect)
And so on, until the next line contains 1's.

But I get WA all times. Please notice that I have solved 108 - Maximum sums sir. manuel
New poster
Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

### 836.-Largest submatrix

Hi, this is my first post, i can´t write english fine, so you have to be patient...

I´m trying to solve the problem 836,,,i use DP,,,the test cases that i input to my solution it´s fine,,,but when i send to the judge i got WA...
I don´t can see my error...can you help me???

Code: Select all

``````ACCEPTED
``````
I did a stupid error,,,

The idea is the same that the problem 108(maximum sum),,,but in this problem, i chance '0' for '-1000', and '1' to 1, and use the code of 108...

triker
New poster
Posts: 5
Joined: Tue Apr 19, 2005 9:56 am

### 836 - Largest Submatrix

I got WA in this problem.
I changed 0 to -1000 and used the same code as 108. (I solved 108).

I have no idea what's wrong. Would you please give the test case that could be incorrect with my code.
Or find out what's wrong with my code?

Code: Select all

``````remove after ac
``````
Here's my test cases

Code: Select all

``````6

111000
111111
111111
111111
111111
011110

11
01

10111000
00010100
00111000
00111010
00111111
01011110
01011110
00011110

1010
0101
1010
0101

0000
0000
0000
0000

111
111
111``````
and output

Code: Select all

``````24

2

16

1

0

9``````
Edit: The problem was wrong output format. I had one more blank line at the last output.

amin__
New poster
Posts: 10
Joined: Thu Jul 01, 2010 10:44 am

### Re: 836 Largest Submatrix

here is my code

#include<cstdio>
#include<cstring>

int main()
{
long T,i,j,k,l,len,len1,max,val,m,n;
int grid;
char str;

scanf("%ld",&T);
getchar();
getchar();
//getchar();

for(i=0;i<T;i++)
{
k=0;
//getchar();
while(1)
{
//scanf("%[^\n]",str);

gets(str);

len=strlen(str);
//if(k==0) len1=len;
if(len==0) break;
for(j=0;j<len;j++)
{
grid[k][j]=str[j]-'0';
}
k++;
}
len1=k;

//printf("%ld %ld\n",k,len1);

/*for(j=0;j<k;j++)
{
for(l=0;l<len1;l++)
{
printf("%ld ",grid[j][l]);
}
printf("\n");
}*/

for(j=0;j<k;j++)
{
for(l=0;l<len1;l++)
{
if(j-1>=0 && l-1>=0)
grid[j][l]+=(grid[j-1][l]+grid[j][l-1]-grid[j-1][l-1]);
else if(j-1>=0)
grid[j][l]+=(grid[j-1][l]);
else if(l-1>=0)
grid[j][l]+=(grid[j][l-1]);
}
}

//printf("\n\n");

max=0;
for(j=0;j<k;j++)
{
for(l=0;l<len1;l++)
{
for(m=j;m<k;m++)
{
for(n=l;n<len1;n++)
{
if(j-1>=0 && l-1>=0)
{
val=(grid[m][n]-grid[j-1][n]-grid[m][l-1]+grid[j-1][l-1]);
}
else if(j-1>=0)
{
val=(grid[m][n]-grid[j-1][n]);
}
else if(l-1>=0)
{
val=(grid[m][n]-grid[m][l-1]);
}
else val=grid[m][n];

//printf("%ld %ld\n\n",val,((n-l)+1)*((m-j)+1));
if(val==((n-l)+1)*((m-j)+1))
{
if(max<((n-l)+1)*((m-j)+1))
{

//printf("%ld %ld\n\n",val,((n-l)+1)*((m-j)+1));
//printf("%ld %ld %ld %ld\n",j,l,m,n);
max=((n-l)+1)*((m-j)+1);
}
}
}
}
}
}
if(i) printf("\n");
printf("%ld\n",max);
//if(i<T-1)
//getchar();

//printf("%ld %ld\n",k,len);

/*for(l=0;l<k;l++)
{
for(j=0;j<len1;j++)
{
printf("%ld",grid[l][j]);
}
printf("\n");
}*/
}

//scanf("%ld",&i);
return 0;
} shoos099
New poster
Posts: 1
Joined: Wed Jun 14, 2017 9:32 pm

### Re: 836 - Largest Submatrix

Hi everyone. I have tested my soulution to this problem with the datasets provided at uDebug (https://www.udebug.com/UVa/836) and it produces the correct output. But I get WA when I sublit. Could anyone help me what's wrong?

Code: Select all

``````#include <iostream>
#include <algorithm>
using namespace std;
//input matrix
#define MAX 25
int A[MAX][MAX]; //current matrix
int N; //size of the matrix

int M[MAX][MAX]; //keep track

void addMatrix(string s, int linenum) {
N = s.size();
for (int c = 0; c < s.size(); c++)
A[linenum - 1][c] = s[c] - '0';
}

int sumSubMatrix(int i1, int j1, int i2, int j2) {
int left, top , corner;
left = top = corner = 0;
int sum = 0;
if (i1 != 0)
top = M[i1 - 1][j2];
if (j1 != 0)
left = M[i2][j1 - 1];
if (i1 != 0 && j1 != 0)
corner = M[i1 - 1][j1 - 1];
sum = M[i2][j2] - top - left + corner;
}

int findMaxSub() {
//first row
M = A;
for (int c = 1; c < N; c++)
M[c] = M[c - 1] + A[c];
//first column
for (int r = 1; r < N; r++)
M[r] = M[r - 1] + A[r];
//other rows and columns
for (int i = 1; i < N; i++) {
for (int j = 1; j < N; j++) {
M[i][j] = M[i - 1][j] + M[i][j - 1] - M[i - 1][j - 1] + A[i][j];
}
}

//search all submatrixs
int max = 0, cur;
for (int i1 = 0; i1 < N; i1++)
for (int i2 = i1; i2 < N; i2++)
for (int j1 = 0; j1 < N; j1++)
for (int j2 = j1; j2 < N; j2++) {
cur = sumSubMatrix(i1, j1, i2, j2);
bool full1 = cur == (i2 - i1 + 1) * (j2 - j1 + 1);
if (cur > max && full1) {
max = cur;
}
}
return max;
}

int main() {
int ncases;
cin >> ncases;

string s;
getline(cin, s);
getline(cin, s);
int linenum = 0;
for (int i = 1; i <= ncases; i++) {

while (getline(cin, s) && !s.empty()) {
linenum++;
}

if (i != 1)
{
cout << endl;
}

cout << findMaxSub() << endl;

linenum = 0;
} //next case
return 0;
}``````