PLEASE, i need some instructions!

[angel16mk]

Hello guys. I'm quite new here, and also i'm begginer in C++ learning. I have some dificulties in solving some tasks, and i need your help, please. I hope i'll get some, and i hope i will improve my C++ knowledge vie this usefull forum.

I have to solve this task:

In matrix of [20][20]. filled with 0(zeros), find the bigest square wich is written with 1???

Visucally guys, it will look something like this:

0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0
0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0
0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0
0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0
0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0
0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

plase, anyone has an idea??

[Albatross]

Hi.

How robust does your algorithm have to be?

In other words, are you sure that the only thing you'll be getting as an input is a 20x20 matrix with rectangles of 1s that are always enclosed by 0s or the edges of your matrix (i.o.w. no touching rectangles or other shapes)?

-Albatross

[angel16mk]

yes, mr. Albatross, i'm sure(the tasks require only that) that the only thing to get as an input is a 20x20 matrix with rectangles of 1s that are always enclosed by 0s or the edges of the matrix.

Plase, Any idea?

[webJose]

Is it rectangles, or is it squares?

Algorithm (basic):

1. Start scanning the first row for a "1".
2. Once the "1" is found, "anchor" there and start moving to the right, counting adjacent "1"'s.
3. Save the total number of "1"'s as the rectangle's width.
4. Starting at the first 1 found in #2, go down counting 1's.
5. Repeat the procedure the same number of times as the rectangle's width; the minimum of all those counts is the rectangle's height.
6. If it was meant to be a square, then pick the minimum between the width and the height and that's your square starting at the coordinates anchored in #2.

This is basic because it would fail to recognize the 4x4 square in:

0 0 1 1 1 1 1 1 0 0
0 0 1 1 1 1 1 1 0 0
0 0 0 0 1 1 1 1 0 0
0 0 0 0 1 1 1 1 0 0

[angel16mk]

it is squares.

i have to say, i'm astonished of your knowledge, i'm looking forward to became a half of you are:) i read your info, nevermind....i am an apsolutely begginer in C++ learning, and i would humble ask you to help me with the algorithm?...the code?...it's structure?...

10x Infornt, MRS Albatross

[webJose]

I already gave you a good basic algorithm and I even pointed out its weakness (in case you would like to improve it). I cannot go any further for now. Take the algorithm I gave you in words and translate it to code yourself.

If you get stuck translating it, then post specific questions here.

[m4ster r0shi]

Apparently, the OP wants to be instructed specifically by M(r)s. Albatross.

[angel16mk]

Any Help is Welcomed, i'm trying to wrote those steps into a code, but it is quite dificult for me..
Tnx WebJose!

[angel16mk]

#include <cstdlib>
#include <iostream>
using namespace std;
int redovi[20];
int temp[20][20];
int GetRed(int i)
{
int count=0;
for (int m = 0; temp[i][m]; m++)
if (temp[i][m])
{
count++;
if(!temp[i][m+1])
break;

}
return count;
}
int GetKol(int j)
{
int count=0;
for (int m = 0; temp[m][j]; m++)
if (temp[m][j])
{
count++;
if(!temp[m+1][j])
break;

}
return count;
}
void IncRedovi()
{
for (int i=0; i<20; i++)
{
redovi[i]=GetRed(i);
}
}
int RandSquare()
{
int max=redovi[0], t=0;
for (int m=1; m<20; m++)
{
if (max<redovi[m])
max=redovi[m],t=m;
}

if (redovi[t]==GetKol(t))
{
cout<<redovi[t];
return redovi[t];
}
else
{redovi[t]=0;
return 0;}
}
int main(int argc, char *argv[])
{
//fill temp[][];
while(RandSquare());
system("PAUSE");
return EXIT_SUCCESS;
}



Please, Where is my mistake??

[angel16mk]

Anyone???

i get this when i tried to compile

BFD 2.15.91 20040904 internal error, aborting at ../../src/bfd/cache.c line 495 in bfd_cache_lookup_worker