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[i] = 0;
///cout << "I equals = " << i << endl;
//cout << "cords[ " << i << "] = " << cords[i] << 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[i] = cords[i];
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[i][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[i][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.
