c++ Recursion programing problem. PLEASE help

[moshe5]

Hi All!

I am currently stuck on a c++ program I'm working on.

So the program will have the user input data into a 2-d array.
sample dialogue:
BLOB SIZE CALCULATOR-
Enter coordinates for each filled cell; e.g 2 3
Do not enter commas or parentheses.
Enter -1 -1 to finish entering cells.

So for user input :
1 1
1 2
2 2
2 3
3 3
3 5
4 1
4 5
5 2
5 5
-1 -1

the output will be:

Grid:
XX___
_XX__
__X_X
X___X
_X_XX

this is easy. the real issue is when I need to output:

55000
05500
00504
20004
02044

The Algorithm needs to calculate all the Blob sizes, and return another grid like the one above.
Algorithm to calculate the size of a blob anchored at a given cell

1. copy the grid (b/c you don't want to use the original)

2. Make a recursive call, using the copy of the grid you made in step 1:
if the cell(x,y) is not in the array then
return 0
else if the cell (x,y) is empty, then
return 0
else
mark the cell (x,y) as empty
return 1+ the count of (x,y)'s 8 neighboring cells
(make 8 recursive calls, one for each neighbor)

so all I can output is the first spot any given blob as the highest number blob- example 0,0 blob will be 5, but the rest won't be 5, since it got turned into 0!!

PLEASE HELP!

#include <iostream>
using namespace std;

void welcomeMessege();
void userInput(int[][5]);
void outputOriginal(const int[][5]);
void returnBlobSize(const int anArray[][5]);
int recursive(int copyArray[][5], int x, int y);

int main()
{
     int originalGrid[5][5]= {0};
     welcomeMessege();
     userInput(originalGrid);
     outputOriginal(originalGrid);
     returnBlobSize(originalGrid);
return 0;
}

void welcomeMessege()
{
     cout << "BLOB SIZE CALCULATOR\n"
             << "Enter coordinates for each filled cell; e.g 2 3\n"
             << "Do not enter commas or parentheses.\n"
             << "Enter -1 -1 to finish entering cells.\n";
}

void userInput(int anArray[][5])
{
     int i = 0, j = 0;
     while(i != -1 || j !=-1)
     {
           cin >> i >> j;
           anArray[i-1][j-1] = 1;
      }
}

void outputOriginal(const int anArray[][5])
{
     cout << "\nOUTPUT OF PROGRAM:\n\n"
             << "Grid:\n";

	int i, j;
	for(i=0; i<5; i++)
	{
	     for(j=0; j<5; j++)
	    {
	          if(anArray[i][j] == 1)
	          {
                                 cout << "X";
	           else
                           {
		 cout << "_";
		 if(j == 4)
		 {
                          	      cout << endl;
		 }
	           }
                    }
                 }

void returnBlobSize(const int anArray[][5])
{
     int copyArray[5][5] = {0};
     int i=0, j=0, x=0, y=0;
     for(i=0; i<5; i++)
     {
          for(j=0; j<5; j++)
         {
	copyArray[i][j] = anArray[i][j]; //array is copied
         }
      }	
      for(x=0; x<5; x++)  //for every square do:
     {
	for(y=0; y<5; y++)
	{
	     copyArray[x][y] = recursive(copyArray, x, y);
	}
      }
	
      cout << endl;	//print array
      for(x=0; x<5; x++)			
     {
            for(y=0; y<5; y++)
           {  
                  cout << copyArray[x][y];
	  if(y==4)
	      cout << endl;
           }
      }
}

int recursive(int copyArray[][5], int x, int y)
{
        if(x<0 || x>4 || y<0 || y>4)
        {
	return 0;
         }
        else if(copyArray[x][y] == 0)
        {
	return 0;
         }
         else 
         {
	copyArray[x][y] = 0;
	return 1 + recursive(copyArray, x-1, y-1)
	              + recursive(copyArray, x-1, y)
	              + recursive(copyArray, x-1, y+1)
	              + recursive(copyArray, x, y-1)
	              + recursive(copyArray, x, y+1)
	              + recursive(copyArray, x+1, y-1)
	              + recursive(copyArray, x+1, y)
	              + recursive(copyArray, x+1, y+1);
         }
}

by the way, the PGM should calculate the sizes of all blobs in the grid. a blob is 1 square with a value of 1 in it, or more touching one another staight up and down or diagnoly. after the pgm goes 1 by 1 to look for value of 1, it will discover 1 eventually and make 8 recursive calls in the squares around it. the problem I have isw that it calculates the blobs, but erases the data for the rest of the current blob- so a blob of 5 will only have 5 in the final output on its FIRST square, and the rest of the squares are now 0's because they were turned into 0's by the algorithm. I need to have them turn back into 1's, whereever they were 1's so all the 5 squares that creat a blob will become 5 as well.

[nucleon]

Firstly, you shouldn't mix tabs and spaces or you get badly formatted code.

To solve your problem, it would be easiest to set the array element to -1 instead of 0 in "recursive". This means you will have to change the previous "else if" clause to

else if (copyArray[x][y] == 0 || copyArray[x][y] == -1)
        return 0;

Then in "returnBlobSize" you would do something like this:

for (x = 0; x < 5; x++)
        for (y = 0; y < 5; y++) {
            n = recursive (copyArray, x, y);
            for (int a = 0; a < 5; a++)
                for (int b = 0; b < 5; b++)
                    if (copyArray[a][b] == -1)
                        copyArray[a][b] = n;
        }

[Lerner]

Here's another angle.

Declare another array to hold the answer. I called it answerArray surprisingly enough. Use it as the left hand side of the following line:

copyArray[x][y] = recursive(copyArray, x, y);

and use it to display the answer.

Then set copyArray to originalArray each time you test a new cell by moving these lines:

for(i=0; i<5; i++)
{
     for(j=0; j<5; j++)
     {
        copyArray[i][j] = anArray[i][j]; //array is copied
      }
 }

so they appear just before this line:

answerArray[x][y] = recursive(copyArray, x, y);

[moshe5]

Here's another angle.

Declare another array to hold the answer. I called it answerArray surprisingly enough. Use it as the left hand side of the following line:

copyArray[x][y] = recursive(copyArray, x, y);

and use it to display the answer.

Then set copyArray to originalArray each time you test a new cell by moving these lines:

for(i=0; i<5; i++)
{
     for(j=0; j<5; j++)
     {
        copyArray[i][j] = anArray[i][j]; //array is copied
      }
 }

so they appear just before this line:

answerArray[x][y] = recursive(copyArray, x, y);

****************************************************
Thanks for your reply!
******************
so the 2nd option is not good, since I can only make 1 copy and use it. the 1st option is something I thought about, and was currently doing, until I realized that I can do something simple as this:

#include <iostream>
using namespace std;

void welcomeMessege();
void userInput(int[][5]);
void outputOriginal(const int[][5]);
void returnBlobSize(const int anArray[][5]);
int recursive(int copyArray[][5], int x, int y);
void copyTheArray(int copyArray[][5], const int anArray[][5]); //this is the change

int main()
{
	int originalGrid[5][5]= {0};
	welcomeMessege();
	userInput(originalGrid);
	
	outputOriginal(originalGrid);
	
	returnBlobSize(originalGrid);

	return 0;

}

void welcomeMessege()
{
	cout << "BLOB SIZE CALCULATOR\n"
	<< "Enter coordinates for each filled cell; e.g 2 3\n"
	 << "Do not enter commas or parentheses.\n"
	 << "Enter -1 -1 to finish entering cells.\n";
}

void userInput(int anArray[][5])
{
	int i = 0, j = 0;
	while(i != -1 || j !=-1)
	{
		cin >> i >> j;
		anArray[i-1][j-1] = 1;
	}
}

void outputOriginal(const int anArray[][5])
{
	cout << "\nOUTPUT OF PROGRAM:\n\n"
		<< "Grid:\n";

	int i, j;
	for(i=0; i<5; i++)
	{
		for(j=0; j<5; j++)
		{
			if(anArray[i][j] == 1)
				cout << "X";
			else
				cout << "_";
			if(j == 4)
				cout << endl;
		}
	}
	cout << "\nBlob sizes:\n";
}

void returnBlobSize(const int anArray[][5])
{
	int copyArray[5][5] = {0};
	int i=0, j=0, x=0, y=0;
	for(i=0; i<5; i++)
	{
		for(j=0; j<5; j++)
		{
		copyArray[i][j] = anArray[i][j]; //array is copied
		}
	}	
	for(x=0; x<5; x++)  //for every square do	{
		for(y=0; y<5; y++)
		{
		copyArray[x][y] = recursive(copyArray, x, y);
		cout << copyArray[x][y]; //this will print   
		if(y==4)                      //the array 1 by 1
		   cout << endl;
		copyTheArray(copyArray, anArray); //copy the 
		}                                                    //array again
	}                                                                   //and proceed
}                                                                                 //to next spot

int recursive(int copyArray[][5], int x, int y)
{
	if(x<0 || x>4 || y<0 || y>4)
	{
		return 0;
	}
	else if(copyArray[x][y] == 0)
	{
		return 0;
	}
	else 
	{
	           copyArray[x][y] = 0;
	           return 1 + recursive(copyArray, x-1, y-1)
		         + recursive(copyArray, x-1, y)
		         + recursive(copyArray, x-1, y+1)
		         + recursive(copyArray, x, y-1)
		         + recursive(copyArray, x, y+1)
		         + recursive(copyArray, x+1, y-1)
		         + recursive(copyArray, x+1, y)
		         + recursive(copyArray, x+1, y+1);
		
	}
}

void copyTheArray(int copyArray[][5], const int anArray[][5])
{
	int i=0, j=0;
	for(i=0; i<5; i++)
	{
		for(j=0; j<5; j++)
		{
		copyArray[i][j] = anArray[i][j]; //array is copied
		}
	}

}

I am still working on it, trying the 1st option or something like it, since I think I might need the array ready to be printed at the end- the -1 instead of 1 could work, but as I mentioned- I tried, and stopped so I will probably have it ready today sometime soon :)

What I have works, but I wil appreciate another idea :)

thanks!!!

[nucleon]

Your current method is very inefficient, copying the array over and over. My original solution is also very inefficient (a quadruple loop!).

A better solution would be to add the blob points to a list (in "recursive") and then go through the list to set their number (after the call to recursive in "returnBlobSize").

If you need to pass a copy of the array to returnBlobSize, copy it like so: memcpy (grid2, grid, DIM*DIM*sizeof(int));

[moshe5]

Your current method is very inefficient, copying the array over and over. My original solution is also very inefficient (a quadruple loop!).

A better solution would be to add the blob points to a list (in "recursive") and then go through the list to set their number (after the call to recursive in "returnBlobSize").

If you need to pass a copy of the array to returnBlobSize, copy it like so: memcpy (grid2, grid, DIM*DIM*sizeof(int));

But can I still do this and follow the guidelines of the project? look at the top of the page. After we studied recursion, we got this project. we just startted lists.

[nucleon]

I didn't mean use a C++ list. Just an array to hold the positions you've discovered. Implement a simple "stack" like the following.

const int SIZE = 5;
const int MAXPOSITIONS = SIZE * SIZE;
struct Position {int x, y;} Position;
Position position[MAXPOSITIONS];
int postop = 0;

int recursive (int grid[][SIZE], int x, int y)
{
  if (not out-of-bounds or grid value 0)

    // Push the position
    if (postop >= MAXPOSITIONS) {
      cerr << "Error: postop\n";
      exit (1);
    }
    position[postop++] = (Position){x, y};

    grid[x][y] = 0;
    ...
}

void returnBlobSize (int grid[][SIZE])
{
  ...
    int n = recursive (grid, x, y);

    // Pop the positions and set the grid values
    while (postop) {
      postop--;
      grid [position[postop].x] [position[postop].y] = n;
    }
}

It may be a good idea to change some names. Change "returnBlobSize" to findBlobs and "recursive" to findBlobAtPoint, for instance.

[moshe5]

Awsome Idea! Using a structure to keep the results, and then print them at the end... :)

But I do need to find out if it is "out of bounds" for this assignment, since the instructions are to use a single copy, and make the changes on it. look at #1 and #2 criteria up in this link. I am going to e-mail my teacher asap and ask for limits.

[moshe5]

another issue is that once you change a square to count it, it is no longer 1 to be counted again. That was the main issue that I encountered, and the only solution I guess is to re-copy the grid once you are done with the first square, and move to the next one.

[Lerner]

>>the only solution I guess is to re-copy the grid once you are done with the first square

Not so fast there. I suspect if you are going to use an array of struct/class to represent the grid, then you can add a variable to the struct/class declaration to denote whether it has been found in a blob already or not ("blobbed") or not. As you loop through the grid if a given cell has been blobbed already then go on to next cell and don't bother rechecking size of blob again. That way you only have to check the size of each blob once and you only have to copy the original array once per program (though it's a bit more code to set up everything you need for the struct/class). You can flip the blobbed variable when you pop the stack and give each cell the stack it's size at the end of each call to recursive and before moving on to the next cell in the grid.