CareerCup

1.If A[m][n] is the given matrix,start from A[1][1].
2.for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
If A[i][j] is set, if true then
If A[i-1][j]&&A[i][j-1]&&A[i-1][j-1] is also set,then
A[i][j]+1

3.Traverse the whole matrix again to find the highest sum. If found at say A[i][j] then row_index=i;col_index=j;
4.for(k=i;k<0;k--)
for(l=j;l<0;l--)
print "1";

Although my language used may not be correct, I hope my logic is understandable and I hope it's right.

1.If A[m][n] is the given matrix,start from A[1][1].
2.for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
If A[i][j] is set, if true then
If A[i-1][j]&&A[i][j-1]&&A[i-1][j-1] is also set,then
A[i][j]+1

3.Traverse the whole matrix again to find the highest sum. If found at say A[i][j] then row_index=i;col_index=j;
4.for(k=i;k<0;k--)
for(l=j;l<0;l--)
print "1";

Although my language used may not be correct, I hope my logic is understandable and I hope it's right.

yeah got the idea

Simply put, this solution:

int n, i, j, answer = 0;
scanf("%d", &n);
for(i = 0; i < n; ++i) {
	scanf("%s", &mx[i]);
	for(j = 0; j < n; ++j)
		if(mx[i][j] == '1')
			size[i][j] = 1;
}
for(i = 1; i < n; ++i)
	for(j = 1; j < n; ++j) {
		if(mx[i][j] == '1')
			size[i][j] = min(size[i][j - 1],
                            min(size[i - 1][j], size[i - 1][j - 1])) + 1;
		if(size[i][j] > answer)
			answer = size[i][j];
	}
for(i = 0; i < answer; ++i) {
	for(j = 0; j < answer; ++j)
		printf("1");
	printf("\n");
}

I am thinking of Knuth Morris Pratt algorithm but modifying the recursive definition accordinly.

working code

#include<iostream>
#define SIZE 5
using namespace std;
int checkthis(int a[][SIZE], int n, int size, int x, int y);
int checkthis(int a[][SIZE], int n, int size, int x, int y)
{
cout<<"size="<<size<<" x="<<x<<" y="<<y<<"\n";
int i=0;
int j=y;
for(i=x;i<=x+size-1;i++) if(a[i][j]==0) return 0;
j=y+size-1;
for(i=x;i<=x+size-1;i++) if(a[i][j]==0 ) return 0;
j=x;
for(i=y;i<=y+size-1;i++) if(a[j][i]==0 ) return 0;
j=x+size-1;
for(i=y;i<=y+size-1;i++) if(a[j][i]==0 ) return 0;

return 1;
}
int findsquares(int a[][SIZE], int n, int size, int &x, int &y );
int findsquares(int a[][SIZE], int n, int size, int &x, int &y )
{
int ret = 0;
for(int i =0; i<=n-size; i++)
for(int j=0; j<=n-size; j++)
{
ret = checkthis(a,n,size,i,j);
if(ret == 1)
{
x=i;
y=j;
return size;
}
}
return 0;
}
int main()
{
int a[SIZE][SIZE] = { 0,0,1,1,0,
1,0,0,1,1,
1,0,0,0,1,
1,1,1,0,1,
1,1,1,1,1};
int x=-1,y=-1;
int k=0;
for(int i=SIZE;i>=1;i--)
{
k=findsquares(a,SIZE,i,x,y);
if(k!=0) break;
}
cout<<"\nbounds:"<<x<<","<<y<<" size:"<<k<<"\n";
return 0;
}