Backtracking Recursion Problem

[NOO Recursion]

Hi everyone! I am trying to write a program that will search a 12x12 for a
thing called a "blob". A blob in the grid is made up of asterisks. A blob
contains at least one asterisk. If an asterisk is in a blob, an asterisk
that is contiguous to it is in the same blob. If a blob has more than two
asterisks, then each asterisk in the blob is contiguous to at least one
other asterisk in the blob. For example this 12x12 grid has 6 blobs. I am
having a heck of a time trying to figure out how to do this with recursion.
I have looked online for examples but all I have found close is maze
problems. The language I am using is C++ and the compiler is Dev C++
4.9.9.2. Any help would be greatly appreciated for I seem to be lost on
this whole recursive thing.

char grid[12][12];

000000000000
0*0000000000
00000*000000
00**0*00000*
00000000000*
00000000000*
0000000**00*
0000000**000
000000000000
000000000***
000000000*0*
000000000***

here is my source code for my whole project if you would like to take a look
at it.

// main.cpp

#include <iostream>
#include "GridIO.h"
#include "Grid.h"

using namespace std;

int main()
{
int cord[24];
int length;
GridIO obj;
obj.getFile();

obj.readAndStore();

Grid Gridobj(obj);
Gridobj.display();

system("PAUSE");
return 0;
}

------------------------------------
//GridIO.cpp

#include <iostream>
#include <cassert>
#include "GridIO.h"

using namespace std;

GridIO::GridIO()
{
for (int i = 0; i <= SIZE; i++)
{
cords = 0;
///cout << "I equals = " << i << endl;
//cout << "cords[ " << i << "] = " << cords << endl;
}
// Default value is the size of the array.
actualSize = SIZE;


} // end of GRIDIO constructor

bool GridIO::getFile()
{
const int INPUTSIZE = 10;
bool retval = false;
char input[INPUTSIZE];
cout << "Please enter the file you would like to open. --> ";
cin >> input;
cout << "You entered: " << input << endl;
infile.open(input);
assert(infile); // make sure file is able to open.
retval = true; // since the assert passed set retval to true.

return retval;
}

void GridIO::readAndStore()
{
// we have cords so start here
int first = 0;
int second = 0;
int index = 0;
char dummy;

infile >> first >> dummy >> second;
while (infile != '\0')
{
cords[index] = first;
index++;
cords[index] = second;
index++;
infile >> first >> dummy >> second;

}
infile.close();
// make sure we were actually able to read something in.
if (index > 0 )
actualSize = index;

index = 0;

while (index < SIZE)
{

cout << cords[index] << endl;
index++;

}
}

void GridIO::getCords(int cord[], int& LENGTH)
{
for (int i = 0; i < SIZE; i++)
cord = cords;
LENGTH = actualSize;

}

------------------------------------------------------
// GridIO.h

#ifndef GRIDIOH
#define GRIDIOH

#include <iostream>
#include <fstream>

using namespace std;

const int SIZE = 100;
class GridIO {

public:
// Purpose: To construct the class and set default values.
// Precondition: NONE
// Postcondition: cords[] array now set to all 0;
// Retruns: NONE
GridIO();

// Purpose: Open user requested file.
// Precondition: File must exist and must be formated according
to
// 2, 3 per line.
// Postcondition: File cords now exist in int cords[] array.
// Returns: True - if file exist.
// False - if file DNE.
bool getFile();

// Purpose: It is to read the file and store the cord in
cords[SIZE].
// Precondition: Must have a file with cords in it.
// Postcondition: File have been read into the array and is
ready to
// to be sent to the grid class.
// Returns: NONE
void readAndStore();

// Purpose: Is to retreive cords and the size of the array from
class
// and give them to the client.
// Precondition: Needs to have a cords[] array that is SIZE
big.
// Postcondition: Files have been copied into client memory.
// Returns: NONE
void getCords(int cord[], int& LENGTH);

private:
fstream infile;
int cords[SIZE];
// Will hold the actual size need for the array based on the
text
// file it has read in.
int actualSize;
};
#endif

-------------------------------------------------
// Grid.h

#ifndef GRIDH
#define GRIDH

#include "GridIO.h"
const int ROW = 12;
const int COL = 12;

class Grid {

public:
// Purpose: Default class constructor. Will set the grid to
all *'s.
// Precondition: NONE
// Postcondition: 12x12 grid now contains all starts.
// Returns: NONE
Grid();

// Purpose: Overloaded Grid constructor. Set the Grid to what
the
// Cords specify.
// Precondition: Must have a char array filled with cords. The
// Size of the array can't exceede *******
// Postcondition: Grid has been set according to the cords.
// Returns: NONE
Grid(GridIO& GridIOobj);

// Purpose: To Display grid.
// Precondition: NONE
// Postcondition: Grid has been displayed on screen.
// Returns: NONE
void display();

// Purpose: Set grid to default setting of 0;
// Precondition: NONE
// Postcondition: Grid now is full of zeros.
// Returns: NONE
void setGridtoZero();

private:
char grid[ROW][COL];

};

#endif


------------------------------------------------------------------------

// Grid.cpp

#include <iostream>
#include "Grid.h"

using namespace std;

Grid::Grid()
{
setGridtoZero();
}

Grid::Grid(GridIO& GridIOobj)
{
const int SIZE = 100;

int row, col = 0;
int rowstart, columstart = 0;
int cords[SIZE];
int Length = 0;
int x = 0;

// initilizes the grid to zero.
setGridtoZero();

GridIOobj.getCords(cords, Length);

cout << "Length is --> " << Length << endl;
cout << "cords " << *cords << endl;

// priming read.
row = cords[x];
x++;
col = cords[x];
x++;

rowstart = (row - 1);
columstart = (col - 1);
// end of priming read.

while (x <= Length)
{
row = cords[x];
x++;
col = cords[x];
x++;

// calculations

if (rowstart > -1 && columstart > -1)
{


cout << "rowstart --> " << rowstart << endl;

cout << "colstart --> " << columstart << endl;
grid[rowstart][columstart] = '*';
rowstart = (row - 1);
columstart = (col - 1);
} // end of if
else
cout << "ERROR - OUT OF BOUNDS!" << endl;
}

}


void Grid::display()
{
for (int i = 0; i<12; i++)
{
cout << endl; // end of line for once the row is done.
for (int j = 0; j<12; j++)
{
cout << grid[j];

}
}
}

void Grid::setGridtoZero()
{
for (int i = 0; i<12; i++)
{
cout << endl;
for (int j = 0; j<12; j++)
{
cout << "Grid[" << i << "][" << j << "]: ";
grid[j] = '0';
}
}
cout << endl;
}

-----------------------------
Anyway, so far the program will read in coordinates from a .dat file that
the user tells us. These coordinates tell the Grid class where the blobs
are located on the 12 x 12 graph called grid[12][12]. After that it will
display what the graph looks like. Of course the next part of the program I
need is the recursive solution that will Identify how many blobs there are
in the graph. As I said up above any help will be greatly appreciated.

 

[=?iso-8859-1?q?Kirit_S=E6lensminde?=]

Hi everyone! I am trying to write a program that will search a 12x12 for a
thing called a "blob". A blob in the grid is made up of asterisks. A blob
contains at least one asterisk. If an asterisk is in a blob, an asterisk
that is contiguous to it is in the same blob. If a blob has more than two
asterisks, then each asterisk in the blob is contiguous to at least one
other asterisk in the blob. For example this 12x12 grid has 6 blobs. I am
having a heck of a time trying to figure out how to do this with recursion.
I have looked online for examples but all I have found close is maze
problems. The language I am using is C++ and the compiler is Dev C++
4.9.9.2. Any help would be greatly appreciated for I seem to be lost on
this whole recursive thing.

char grid[12][12];

000000000000
0*0000000000
00000*000000
00**0*00000*
00000000000*
00000000000*
0000000**00*
0000000**000
000000000000
000000000***
000000000*0*
000000000***
[snip]
-----------------------------
Anyway, so far the program will read in coordinates from a .dat file that
the user tells us. These coordinates tell the Grid class where the blobs
are located on the 12 x 12 graph called grid[12][12]. After that it will
display what the graph looks like. Of course the next part of the program I
need is the recursive solution that will Identify how many blobs there are
in the graph. As I said up above any help will be greatly appreciated.

Look up graphics algorithms for doing flood filling. They will show
how to work out contiguous areas of the sort you're after.

They're not good things to do recursively though. You should use a
separate stack to store intermediate results rather than the program
stack because the heap is so much larger than than the program stack.
For a 12x12 grid it probably won't matter, but it's a bad habit to get
into. Here's a link describing this in detail:

http://www.kirit.com/Recursive rights and wrongs


K

 

[paul.joseph.davis]

Hi everyone! I am trying to write a program that will search a 12x12 for a
thing called a "blob". A blob in the grid is made up of asterisks. A blob
contains at least one asterisk. If an asterisk is in a blob, an asterisk
that is contiguous to it is in the same blob. If a blob has more than two
asterisks, then each asterisk in the blob is contiguous to at least one
other asterisk in the blob. For example this 12x12 grid has 6 blobs. I am
having a heck of a time trying to figure out how to do this with recursion.
I have looked online for examples but all I have found close is maze
problems. The language I am using is C++ and the compiler is Dev C++
4.9.9.2. Any help would be greatly appreciated for I seem to be lost on
this whole recursive thing.

char grid[12][12];

000000000000
0*0000000000
00000*000000
00**0*00000*
00000000000*
00000000000*
0000000**00*
0000000**000
000000000000
000000000***
000000000*0*
000000000***

here is my source code for my whole project if you would like to take a look
at it.

// main.cpp

#include <iostream>
#include "GridIO.h"
#include "Grid.h"

using namespace std;

int main()
{
int cord[24];
int length;
GridIO obj;
obj.getFile();

obj.readAndStore();

Grid Gridobj(obj);
Gridobj.display();

system("PAUSE");
return 0;

}

------------------------------------
//GridIO.cpp

#include <iostream>
#include <cassert>
#include "GridIO.h"

using namespace std;

GridIO::GridIO()
{
for (int i = 0; i <= SIZE; i++)
{
cords = 0;
///cout << "I equals = " << i << endl;
//cout << "cords[ " << i << "] = " << cords << endl;
}
// Default value is the size of the array.
actualSize = SIZE;

} // end of GRIDIO constructor

bool GridIO::getFile()
{
const int INPUTSIZE = 10;
bool retval = false;
char input[INPUTSIZE];
cout << "Please enter the file you would like to open. --> ";
cin >> input;
cout << "You entered: " << input << endl;
infile.open(input);
assert(infile); // make sure file is able to open.
retval = true; // since the assert passed set retval to true.

return retval;

}

void GridIO::readAndStore()
{
// we have cords so start here
int first = 0;
int second = 0;
int index = 0;
char dummy;

infile >> first >> dummy >> second;
while (infile != '\0')
{
cords[index] = first;
index++;
cords[index] = second;
index++;
infile >> first >> dummy >> second;

}
infile.close();
// make sure we were actually able to read something in.
if (index > 0 )
actualSize = index;

index = 0;

while (index < SIZE)
{

cout << cords[index] << endl;
index++;

}

}

void GridIO::getCords(int cord[], int& LENGTH)
{
for (int i = 0; i < SIZE; i++)
cord = cords;
LENGTH = actualSize;

}

------------------------------------------------------
// GridIO.h

#ifndef GRIDIOH
#define GRIDIOH

#include <iostream>
#include <fstream>

using namespace std;

const int SIZE = 100;
class GridIO {

public:
// Purpose: To construct the class and set default values.
// Precondition: NONE
// Postcondition: cords[] array now set to all 0;
// Retruns: NONE
GridIO();

// Purpose: Open user requested file.
// Precondition: File must exist and must be formated according
to
// 2, 3 per line.
// Postcondition: File cords now exist in int cords[] array.
// Returns: True - if file exist.
// False - if file DNE.
bool getFile();

// Purpose: It is to read the file and store the cord in
cords[SIZE].
// Precondition: Must have a file with cords in it.
// Postcondition: File have been read into the array and is
ready to
// to be sent to the grid class.
// Returns: NONE
void readAndStore();

// Purpose: Is to retreive cords and the size of the array from
class
// and give them to the client.
// Precondition: Needs to have a cords[] array that is SIZE
big.
// Postcondition: Files have been copied into client memory.
// Returns: NONE
void getCords(int cord[], int& LENGTH);

private:
fstream infile;
int cords[SIZE];
// Will hold the actual size need for the array based on the
text
// file it has read in.
int actualSize;};

#endif

-------------------------------------------------
// Grid.h

#ifndef GRIDH
#define GRIDH

#include "GridIO.h"
const int ROW = 12;
const int COL = 12;

class Grid {

public:
// Purpose: Default class constructor. Will set the grid to
all *'s.
// Precondition: NONE
// Postcondition: 12x12 grid now contains all starts.
// Returns: NONE
Grid();

// Purpose: Overloaded Grid constructor. Set the Grid to what
the
// Cords specify.
// Precondition: Must have a char array filled with cords. The
// Size of the array can't exceede *******
// Postcondition: Grid has been set according to the cords.
// Returns: NONE
Grid(GridIO& GridIOobj);

// Purpose: To Display grid.
// Precondition: NONE
// Postcondition: Grid has been displayed on screen.
// Returns: NONE
void display();

// Purpose: Set grid to default setting of 0;
// Precondition: NONE
// Postcondition: Grid now is full of zeros.
// Returns: NONE
void setGridtoZero();

private:
char grid[ROW][COL];

};

#endif

------------------------------------------------------------------------

// Grid.cpp

#include <iostream>
#include "Grid.h"

using namespace std;

Grid::Grid()
{
setGridtoZero();

}

Grid::Grid(GridIO& GridIOobj)
{
const int SIZE = 100;

int row, col = 0;
int rowstart, columstart = 0;
int cords[SIZE];
int Length = 0;
int x = 0;

// initilizes the grid to zero.
setGridtoZero();

GridIOobj.getCords(cords, Length);

cout << "Length is --> " << Length << endl;
cout << "cords " << *cords << endl;

// priming read.
row = cords[x];
x++;
col = cords[x];
x++;

rowstart = (row - 1);
columstart = (col - 1);
// end of priming read.

while (x <= Length)
{
row = cords[x];
x++;
col = cords[x];
x++;

// calculations

if (rowstart > -1 && columstart > -1)
{

cout << "rowstart --> " << rowstart << endl;

cout << "colstart --> " << columstart << endl;
grid[rowstart][columstart] = '*';
rowstart = (row - 1);
columstart = (col - 1);
} // end of if
else
cout << "ERROR - OUT OF BOUNDS!" << endl;
}

}

void Grid::display()
{
for (int i = 0; i<12; i++)
{
cout << endl; // end of line for once the row is done.
for (int j = 0; j<12; j++)
{
cout << grid[j];

}
}

}

void Grid::setGridtoZero()
{
for (int i = 0; i<12; i++)
{
cout << endl;
for (int j = 0; j<12; j++)
{
cout << "Grid[" << i << "][" << j << "]: ";
grid[j] = '0';
}
}
cout << endl;
}

-----------------------------
Anyway, so far the program will read in coordinates from a .dat file that
the user tells us. These coordinates tell the Grid class where the blobs
are located on the 12 x 12 graph called grid[12][12]. After that it will
display what the graph looks like. Of course the next part of the program I
need is the recursive solution that will Identify how many blobs there are
in the graph. As I said up above any help will be greatly appreciated.

Backtracking isn't the algorithm you should be using for this problem.
Its usually used as a brute-force search for a set a of values that
satisfy some criterion. Its used to solve things like sudoku puzzles
and the n-queens problem.

Check this link for more information.
http://en.wikipedia.org/wiki/Backtracking

And you don't even necessarily need to use recursion to solve this
problem either if you go with the breadth first search. But anyway, on
to some things that might help:

This is a standard graph-connectivity problem. See the references
below:

http://mathworld.wolfram.com/ConnectedGraph.html
http://en.wikipedia.org/wiki/Connectedness
http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK2/NODE63.HTM#graphtraversal

Each asterisk is a node in the graph. When two asterisks are adjacent,
consider that an edge. With that in mind, when you read in the data,
create your nodes and edges. Then go through and mark each one using
a breadth first or depth first search.

http://en.wikipedia.org/wiki/Depth-first_search
http://en.wikipedia.org/wiki/Breadth-first_search

Pseudo code at:
http://www.kirupa.com/developer/actionscript/depth_breadth_search.htm

Durring your search you mark each node as visited with a label unique
to each group. Then you figure out how many labels you used and
you've got the number of blobs.

HTH,
Paul Davis

 

[John Harrison]

Hi everyone! I am trying to write a program that will search a 12x12 for a
thing called a "blob". A blob in the grid is made up of asterisks. A blob
contains at least one asterisk. If an asterisk is in a blob, an asterisk
that is contiguous to it is in the same blob. If a blob has more than two
asterisks, then each asterisk in the blob is contiguous to at least one
other asterisk in the blob. For example this 12x12 grid has 6 blobs. I am
having a heck of a time trying to figure out how to do this with recursion.
I have looked online for examples but all I have found close is maze
problems. The language I am using is C++ and the compiler is Dev C++
4.9.9.2. Any help would be greatly appreciated for I seem to be lost on
this whole recursive thing.

Recursion is easy once you get the hang of it. Here's some psuedo-code

find_blob(x, y, blob)
{
if (in_grid(x, y) && grid[x][y] == '*' && !in_blob(blob, x, y))
{
add_to_blob(blob, x, y);
find_blob(x + 1, y, blob);
find_blob(x - 1, y, blob);
find_blob(x, y + 1, blob);
find_blob(x, y - 1, blob);
}
}

That's all there is to it. x and y are your cordinates, blob is some
sort of data structure where you store the x and y coordinates that form
a blob. add_to_blob adds a pair of coordinate to the blob, in_blob
checks if a pair of x and y coordinates are already in a blob (so you
don't add the same coordinates twice and get into an inifinite loop).
Finally in_grid checks if x and y are inside the grid, so you don't fall
over the edge of the grid. Easy (but untested).

As you've been told this may not be the most efficient method, but I
guess the purpose of the exercise is to learn recursion.

Try coding up the pseudo-code above and come back if you have any problems.

john

 

[John Harrison]

Incidentally the above code involves recursion but no backtracking. I'm
not sure where you got the idea that backtracking is necessary.

 

[red floyd]

Incidentally the above code involves recursion but no backtracking. I'm
not sure where you got the idea that backtracking is necessary.

Most likely from the homework assignment. However, he did post his code
and his specific problem.

 

[NOO Recursion]

Thanks everyone! I will take a look at all your post after work today. I
will get back to you sometime tommorrow to tell you how it went. Thanks
again!

 

[Andrey Tarasevich]

...
I am
having a heck of a time trying to figure out how to do this with recursion.
...

There's a terminological issue here that needs to be resolved first: what
exactly do you mean by "recursion" here?

If you specifically need a C++ program that will simply contain a function that
calls itself, then you are talking about mere "syntactical" recursion. It is
rather strange to see a _requirement_ to use this kind of recursion anywhere
besides a homework assignment, because in practical real-life cases it might be
a good idea to avoid syntactical recursion in solving problems like that.

If you are talking about algorithmic recursion (i.e. "recursion" as a particular
flavor of divide-and-conquer approach in algorithm design), then it is a
different story. This problem can indeed be easily solved by a D&C algorithm,
but frankly, I don't see the actual need for the _recursive_ variety of D&C.
There's no need to force the depth-first traversal and there's no need for
backtracking (why are you mentioning it in the subject?), which normally means
that there's no need for recursive D&C.

So, what exactly do you mean by "recursion" anyway?

 

[NOO Recursion]

I am writing up my recursive solution to the problem. Thanks everyone you
have all helped a lot. Ohh, and John thanks I am looking into your
psuedo-code as a starting point for my solution. Seriously it has helped me
figure out were to start on this. I will post my code when I am done.
Thanks again.

Hi everyone! I am trying to write a program that will search a 12x12
for a thing called a "blob". A blob in the grid is made up of asterisks.
A blob contains at least one asterisk. If an asterisk is in a blob, an
asterisk that is contiguous to it is in the same blob. If a blob has
more than two asterisks, then each asterisk in the blob is contiguous to
at least one other asterisk in the blob. For example this 12x12 grid has
6 blobs. I am having a heck of a time trying to figure out how to do
this with recursion. I have looked online for examples but all I have
found close is maze problems. The language I am using is C++ and the
compiler is Dev C++ 4.9.9.2. Any help would be greatly appreciated for I
seem to be lost on this whole recursive thing.

Recursion is easy once you get the hang of it. Here's some psuedo-code

find_blob(x, y, blob)
{
if (in_grid(x, y) && grid[x][y] == '*' && !in_blob(blob, x, y))
{
add_to_blob(blob, x, y);
find_blob(x + 1, y, blob);
find_blob(x - 1, y, blob);
find_blob(x, y + 1, blob);
find_blob(x, y - 1, blob);
}
}

That's all there is to it. x and y are your cordinates, blob is some sort
of data structure where you store the x and y coordinates that form a
blob. add_to_blob adds a pair of coordinate to the blob, in_blob checks if
a pair of x and y coordinates are already in a blob (so you don't add the
same coordinates twice and get into an inifinite loop). Finally in_grid
checks if x and y are inside the grid, so you don't fall over the edge of
the grid. Easy (but untested).

As you've been told this may not be the most efficient method, but I guess
the purpose of the exercise is to learn recursion.

Try coding up the pseudo-code above and come back if you have any
problems.

john

 

[NOO Recursion]

Hi everyone, I have written what I think is a recursive solution to my blob
problem. Ohh and to the previous post I have to do this recursively because
it is required in the assignment. Anyway the only problem is that I can't
figure out how to get it to score correctly. For some reason it just counts
all the blobs in the grid instead of following the rules of what a blob is.
Here is the recursive function. Thanks again!

-------------------------------------
// grid and blob are private data members of the Blob class.
int Blob::find_blob(int x, int y)
{
cout << "Launch" << endl;

if (in_grid(x, y) && grid[x][y] == '*' && !is_flaged(x, y))
{
add_to_blob(x, y);
find_blob(x + 1, y); // DOWN
find_blob(x - 1, y); // UP
find_blob(x, y + 1); // Right
find_blob(x, y - 1); // Left
numofBlobs++; // A blob has been found.
} // end if
else
cout << "NO" << endl;



cout << "OUT" << endl;
return numofBlobs;
}

As far as I can tell it seems like the recursion does what I want it to do.
This code is based off Johns post way below. He does a good job of
describing what the function does. Anyway if anyone could tell me what I am
doing wrong with the scoring it would be greatly appreciated. Thanks


Here is all the code I have so far.

----------------------------------------
// main.cpp
#include <iostream>
#include "GridIO.h"
#include "Grid.h"
#include "Blob.h"

using namespace std;

int main()
{
int cord[24];
int length;
char grid[12][12];
GridIO obj;
obj.getFile();

obj.readAndStore();

Grid Gridobj(obj);
Gridobj.display();

Gridobj.getGrid(grid);
//cout << grid[0][0] << endl;
// More test code
Blob blobObj(Gridobj);
//bool test;
// test = blobObj.in_grid(1,0);
blobObj.searchGrid();


// if (test)
// cout << "yes in grid!" << endl;
//else
// cout << "NO, not in grid!" << endl;

// end




// TESTING OF server to client information sharing of the cords.
//obj.getCords(cord, length);



// for (int i = 0; i < 24; i++)
// cout << "cords are --> " << cord << endl;

// cout << "The size is --> " << length << endl;

// END TEST.

//Grid gridObj;
// gridObj.display();




system("PAUSE");
return 0;
}

----------------------------------------------------------------

// GridIO.cpp

#include <iostream>
#include <cassert>
#include "GridIO.h"

using namespace std;

GridIO::GridIO()
{
for (int i = 0; i <= SIZE; i++)
{
cords = 0;
///cout << "I equals = " << i << endl;
//cout << "cords[ " << i << "] = " << cords << endl;
}
// Default value is the size of the array.
actualSize = SIZE;


} // end of GRIDIO constructor

bool GridIO::getFile()
{
const int INPUTSIZE = 10;
bool retval = false;
char input[INPUTSIZE];
cout << "Please enter the file you would like to open. --> ";
cin >> input;
cout << "You entered: " << input << endl;
infile.open(input);
assert(infile); // make sure file is able to open.
retval = true; // since the assert passed set retval to true.

return retval;
}

void GridIO::readAndStore()
{
// we have cords so start here
int first = 0;
int second = 0;
int index = 0;
char dummy;

infile >> first >> dummy >> second;
while (infile != '\0')
{
cords[index] = first;
index++;
cords[index] = second;
index++;
infile >> first >> dummy >> second;

}
infile.close();
// make sure we were actually able to read something in.
if (index > 0 )
actualSize = index;

index = 0;

while (index < SIZE)
{

cout << cords[index] << endl;
index++;

}
}

void GridIO::getCords(int cord[], int& LENGTH)
{
for (int i = 0; i < SIZE; i++)
cord = cords;
LENGTH = actualSize;

}

--------------------------------------------------------------------
// GridIO.h
#ifndef GRIDIOH
#define GRIDIOH

#include <iostream>
#include <fstream>

using namespace std;

const int SIZE = 100;
class GridIO {

public:
// Purpose: To construct the class and set default values.
// Precondition: NONE
// Postcondition: cords[] array now set to all 0;
// Retruns: NONE
GridIO();

// Purpose: Open user requested file.
// Precondition: File must exist and must be formated according
to
// 2, 3 per line.
// Postcondition: File cords now exist in int cords[] array.
// Returns: True - if file exist.
// False - if file DNE.
bool getFile();

// Purpose: It is to read the file and store the cord in
cords[SIZE].
// Precondition: Must have a file with cords in it.
// Postcondition: File have been read into the array and is
ready to
// to be sent to the grid class.
// Returns: NONE
void readAndStore();

// Purpose: Is to retreive cords and the size of the array from
class
// and give them to the client.
// Precondition: Needs to have a cords[] array that is SIZE
big.
// Postcondition: Files have been copied into client memory.
// Returns: NONE
void getCords(int cord[], int& LENGTH);

private:
fstream infile;
int cords[SIZE];
// Will hold the actual size need for the array based on the
text
// file it has read in.
int actualSize;
};
#endif

------------------------------------------------------------------------------
// grid.h
#ifndef GRIDH
#define GRIDH

#include "GridIO.h"
const int ROW = 12;
const int COL = 12;

class Grid {

public:
// Purpose: Default class constructor. Will set the grid to
all *'s.
// Precondition: NONE
// Postcondition: 12x12 grid now contains all starts.
// Returns: NONE
Grid();

// Purpose: Overloaded Grid constructor. Set the Grid to what
the
// Cords specify.
// Precondition: Must have a char array filled with cords. The
// Size of the array can't exceede *******
// Postcondition: Grid has been set according to the cords.
// Returns: NONE
Grid(GridIO& GridIOobj);

// Purpose: To Display grid.
// Precondition: NONE
// Postcondition: Grid has been displayed on screen.
// Returns: NONE
void display();

// Purpose: Set grid to default setting of 0;
// Precondition: NONE
// Postcondition: Grid now is full of zeros.
// Returns: NONE
void setGridtoZero();

// Purpose: Is to allow the client to get a copy of the stored
grid.
// Precondition: Must have a character array.
// Postcondition: Client now has a copy of the grid and the
size of it.
// Returns: NONE
void getGrid(char copyGrid[ROW][COL]);

private:
char grid[ROW][COL];

};

#endif
-------------------------------------------------------------------------------

// grid.cpp

#include <iostream>
#include "Grid.h"

using namespace std;

Grid::Grid()
{
setGridtoZero();
}

Grid::Grid(GridIO& GridIOobj)
{
const int SIZE = 100;

int row, col = 0;
int rowstart, columstart = 0;
int cords[SIZE];
int Length = 0;
int x = 0;

// initilizes the grid to zero.
setGridtoZero();

GridIOobj.getCords(cords, Length);

cout << "Length is --> " << Length << endl;
cout << "cords " << *cords << endl;

// priming read.
row = cords[x];
x++;
col = cords[x];
x++;

rowstart = (row - 1);
columstart = (col - 1);
// end of priming read.

while (x <= Length)
{
row = cords[x];
x++;
col = cords[x];
x++;

// calculations

if (rowstart > -1 && columstart > -1)
{


cout << "rowstart --> " << rowstart << endl;

cout << "colstart --> " << columstart << endl;
grid[rowstart][columstart] = '*';
rowstart = (row - 1);
columstart = (col - 1);
} // end of if
else
cout << "ERROR - OUT OF BOUNDS!" << endl;
}

}


void Grid::display()
{
for (int i = 0; i<12; i++)
{
cout << endl; // end of line for once the row is done.
for (int j = 0; j<12; j++)
{
cout << grid[j];

}
}
}

void Grid::setGridtoZero()
{
for (int i = 0; i<12; i++)
{
cout << endl;
for (int j = 0; j<12; j++)
{
cout << "Grid[" << i << "][" << j << "]: ";
grid[j] = '0';
}
}
cout << endl;
}

void Grid::getGrid(char copyGrid[ROW][COL])
{
for (int i = 0; i<12; i++)
{
for (int j = 0; j<12; j++)
{
copyGrid[j] = grid[j];
}
}

}
-------------------------------------------------------------------------------

// Blob.cpp
#include <iostream>
#include "Blob.h"
#include "Grid.h"

using namespace std;

Blob::Blob(Grid& gridObj)
{
setGridtoZero();
gridObj.getGrid(grid);
numofBlobs = 0;
}

void Blob::setGridtoZero()
{
for (int i = 0; i<12; i++)
{
for (int j = 0; j<12; j++)
{
//cout << "Grid[" << i << "][" << j << "]: ";
blob[j] = '0';
}
}
}

bool Blob::in_grid(int x, int y)
{
bool retval = false;

if (x >= 0 && y >= 0 && x <= 12 && y <= 12)
retval = true;

return retval;
}

int Blob::find_blob(int x, int y)
{
cout << "Launch" << endl;

if (in_grid(x, y) && grid[x][y] == '*' && !is_flaged(x, y))
{
add_to_blob(x, y);
find_blob(x + 1, y); // DOWN
find_blob(x - 1, y); // UP
find_blob(x, y + 1); // Right
find_blob(x, y - 1); // Left
numofBlobs++; // A blob has been found.

} // end if
else
cout << "NO" << endl;



cout << "OUT" << endl;
return numofBlobs;
}

void Blob::searchGrid()
{
int blobs = 0;
for (int i = 0; i<12; i++)
{ // row
cout << endl; // end of line for once the row is done.
for (int j = 0; j<12; j++)
{ // col
if (grid[j] == '*' && !is_flaged(i,j))
{
cout << "Star found at --> Grid[" << i << "][" << j
<< "]: " << endl;
blobs = find_blob(i, j);
} // end of if

}// end inner for

} // end outer for

cout << "blobs found --> " << blobs << endl;
}

bool Blob::is_flaged(int x, int y)
{
bool retVal = false;
if (blob[x][y] == '*')
retVal = true;
return retVal;
}
void Blob::add_to_blob(int x, int y)
{
cout << "cords to be added are x == " << x << "y == " << y << endl;
blob[x][y] = '*';
}

---------------------------------------------------------------
// Blob.h

#ifndef BLOBH
#define BLOBH

#include "Grid.h"

const int ROWS = 12;
const int COLS = 12;


class Blob {

public:
// Purpose: To give the blob class access to the Grid Class so
that
// It may identify the number of blobs in the grid.
// Precondition: The grid class must have a 12x12 grid
containing the
// blobs in it.
// Postcondition: The blob class now may access the public
functions
// of the grid class.
// Returns: NONE
Blob(Grid& gridObj);

// Purpose: Set grid to default setting of 0;
// Precondition: NONE
// Postcondition: Grid now is full of zeros.
// Returns: NONE
void setGridtoZero();

// Purpose: To check to see if your coordinates are inside the
grid.
// Precondition: Needs a x cord and a y cord. Both must be
integers.
// Postcondition: The x and y cords have been compared to the
exceptable
// Range of cords.
// Returns: True: If cords are inside the gride
// False: If they are not inside the gride.
bool in_grid(int x, int y);

// Purpose: To see if the blob has already been labled as
found.
// Precondition: blob[][] must be a blank character array.
// Postcondition: blob[][] has been checked to see if a blob
has been
// found.
// Returns: True - if blob already has been found.
// False - if blob has not been found.
//bool in_blob(char blob[][], int x, int y);
bool is_flaged(int x, int y);

// Purpose: Is to add the found blobs to the blob array. That
way
// We have a array to compare the found and not found
blobs
// to.
// Precondition: Needs to have a char array size 12 x 12.
// Postcondition: A blob has been marked in char blob[x][y].
// Returns: NONE
void add_to_blob(int x, int y);

// Purpose: Is to search the grid for blobs.
// Precondition: NONE
// Postcondition: Grid has been searched
// Returns: NONE
void searchGrid();

// Purpose: To find the # of blobs in the grid and return them.
// Precondition: NONE.
// Postcondition: The amount of blobs have been found.
// Returns: NONE
// int find_blob(int x, int y, char blob[][]);
int find_blob(int x, int y);



// Purpose: To display grid.
// Precondition: NONE
// Postcondition: NONE
// Returns: NONE

void displayGrid();

private:
char grid[ROWS][COLS]; // grid that will be evaluated.
char blob[ROWS][COLS]; // will hold the location of
blobs found
int numofBlobs; // will hold number of blobs found

}; // END BLOB CLASS
#endif

Hi everyone! I am trying to write a program that will search a 12x12
for a thing called a "blob". A blob in the grid is made up of asterisks.
A blob contains at least one asterisk. If an asterisk is in a blob, an
asterisk that is contiguous to it is in the same blob. If a blob has
more than two asterisks, then each asterisk in the blob is contiguous to
at least one other asterisk in the blob. For example this 12x12 grid has
6 blobs. I am having a heck of a time trying to figure out how to do
this with recursion. I have looked online for examples but all I have
found close is maze problems. The language I am using is C++ and the
compiler is Dev C++ 4.9.9.2. Any help would be greatly appreciated for I
seem to be lost on this whole recursive thing.

Recursion is easy once you get the hang of it. Here's some psuedo-code

find_blob(x, y, blob)
{
if (in_grid(x, y) && grid[x][y] == '*' && !in_blob(blob, x, y))
{
add_to_blob(blob, x, y);
find_blob(x + 1, y, blob);
find_blob(x - 1, y, blob);
find_blob(x, y + 1, blob);
find_blob(x, y - 1, blob);
}
}

That's all there is to it. x and y are your cordinates, blob is some sort
of data structure where you store the x and y coordinates that form a
blob. add_to_blob adds a pair of coordinate to the blob, in_blob checks if
a pair of x and y coordinates are already in a blob (so you don't add the
same coordinates twice and get into an inifinite loop). Finally in_grid
checks if x and y are inside the grid, so you don't fall over the edge of
the grid. Easy (but untested).

As you've been told this may not be the most efficient method, but I guess
the purpose of the exercise is to learn recursion.

Try coding up the pseudo-code above and come back if you have any
problems.

john

 

[John Harrison]

Hi everyone, I have written what I think is a recursive solution to my blob
problem. Ohh and to the previous post I have to do this recursively because
it is required in the assignment. Anyway the only problem is that I can't
figure out how to get it to score correctly. For some reason it just counts
all the blobs in the grid instead of following the rules of what a blob is.
Here is the recursive function. Thanks again!

OK, by score I guess you mean trying to count the number of blobs?

The problem is that you are counting the number of blobs inside the
recursive function, so it's counting asterisks, instead of blobs.

To count blobs you just need to rewrite your code so that you increase
the count when you start finding a blob, not each time that find a bit
more of a blob.

Get rid of the numofBlobs from the class, change find_blob so that's it
a void function and then rewrite searchGrid as below.

Also you have a bug in in_grid, see below

void Blob::searchGrid()
{
int blobs = 0;
for (int i = 0; i<12; i++)
{ // row
cout << endl; // end of line for once the row is done.
for (int j = 0; j<12; j++)
{ // col
if (grid[j] == '*' && !is_flaged(i,j))
{
cout << "Star found at --> Grid[" << i << "][" << j
<< "]: " << endl;
blobs = find_blob(i, j);

find_blob(i, j);
++blobs;

} // end of if

}// end inner for

} // end outer for

cout << "blobs found --> " << blobs << endl;
}

bool Blob::in_grid(int x, int y)
{
bool retval = false;

if (x >= 0 && y >= 0 && x <= 12 && y <= 12)
retval = true;

return retval;
}

Should be x < 12 && y < 12. Also as a style issue you can get rid of the
variable retval, and just write

bool Blob::in_grid(int x, int y)
{
return x >= 0 && y >= 0 && x < 12 && y < 12;
}

All changes from just eyeballing your code, I haven't run anything, so I
might have got things wrong.

john

 

[NOO Recursion]

Thanks, I will try it out latter today. I will let you know how it went.

Hi everyone, I have written what I think is a recursive solution to my
blob problem. Ohh and to the previous post I have to do this recursively
because it is required in the assignment. Anyway the only problem is
that I can't figure out how to get it to score correctly. For some
reason it just counts all the blobs in the grid instead of following the
rules of what a blob is. Here is the recursive function. Thanks again!

OK, by score I guess you mean trying to count the number of blobs?

The problem is that you are counting the number of blobs inside the
recursive function, so it's counting asterisks, instead of blobs.

To count blobs you just need to rewrite your code so that you increase the
count when you start finding a blob, not each time that find a bit more of
a blob.

Get rid of the numofBlobs from the class, change find_blob so that's it a
void function and then rewrite searchGrid as below.

Also you have a bug in in_grid, see below

void Blob::searchGrid()
{
int blobs = 0;
for (int i = 0; i<12; i++)
{ // row
cout << endl; // end of line for once the row is done.
for (int j = 0; j<12; j++)
{ // col
if (grid[j] == '*' && !is_flaged(i,j))
{
cout << "Star found at --> Grid[" << i << "][" <<
j << "]: " << endl;
blobs = find_blob(i, j);

find_blob(i, j);
++blobs;

} // end of if

}// end inner for

} // end outer for

cout << "blobs found --> " << blobs << endl;
}

bool Blob::in_grid(int x, int y)
{
bool retval = false;

if (x >= 0 && y >= 0 && x <= 12 && y <= 12)
retval = true;

return retval;
}

Should be x < 12 && y < 12. Also as a style issue you can get rid of the
variable retval, and just write

bool Blob::in_grid(int x, int y)
{
return x >= 0 && y >= 0 && x < 12 && y < 12;
}

All changes from just eyeballing your code, I haven't run anything, so I
might have got things wrong.

john

 

[NOO Recursion]

Things went well! Everything works and I was able to turn in the assignment
on-time. Thanks for your help. I now have a much better understanding of
recursion.

latter today. I will let you know how it went.