Re: Backtracking Recursion Problem

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.