Solved

Run time error in recursive function

Posted on 2004-09-24
1
174 Views
Last Modified: 2010-04-01
Hi there.

I'm writing a program which reads in a boolean grid from a TXT file and finds groups of "true" values called blobs.

It includes a recursive function which finds the size of a blob at any grid point. A run time error occurs in the program and I believe it is due to a mistake in this function, called "getBlobSize".

Here is the source code:

#include <iostream>
#include <cstdlib>
#include <string>
#include <fstream>
#include <vector>

using namespace std;

class grid
{
  // A class which manipulates a 2-dimensional grid of bool
 
   public :
       grid();  
       // default constructor - initialises variables
       void readGrid(string filename);
       // precondition : none
       // postcondition :
       // if a file called filename exists then the file of grid
       // data has been read in
       // otherwise the message  "File does not exist" is
       // displayed
       void printGrid();
       // displays the grid data with each row on a new line
       int getMaxBlob();
       // precondition : isEmpty is false and findAllBlobs has been invoked
       // postcondition : returns the size of the maximum blob
       bool isEmpty();
       // returns true if grid data is empty (not successfully read in)
       // and otherwise false
       void findAllBlobs();
       // precondition : isEmpty is false
       // postcondition : the size of each blob has been determined
       // and displayed (integers separated by tabs)
       // the maximum blob size has been determined.
       
   protected :
       int getBlobSize(int curRow, int curCol);
       // recursive function called by findAllBlobs()
       // returns the size of the current blob
       // (a blob starting at row CurRow and column curCol).

   private :
       vector < vector <bool> >  v;   // the 2-dimensional grid of data
       int rows;                      // the number of rows in the grid data
       int cols;                      // the number of columns in the grid data
       int maxBlob;                   // the size of the maximum blob found
                                      // (set by findAllBlobs())
};    

int main()
{
  grid mainGrid;
  string file;                                      
 
  cout << "Enter filename" << endl;
  cin >> file;                        // type data.txt
  mainGrid.readGrid(file);
 
  if (!mainGrid.isEmpty())
  {
    mainGrid.printGrid();

    mainGrid.findAllBlobs();
 
    cout << "The maximum blob size is " << mainGrid.getMaxBlob() << endl;
  }

  system("PAUSE");
  return 0;
}

grid::grid()
{
  rows = 0;
  cols = 0;
  maxBlob = 0;
}

void grid::readGrid(string filename)
{
  char cell;
 
  ifstream inFile;
 
  inFile.open(filename.c_str());
 
  if (!inFile)
    cout << "File does not exist" << endl;
  else
  {
    inFile >> rows >> cols;
   
    v.resize(rows, vector <bool> (cols, false));
   
    for (int i=0; i < rows; i++)
    {  
      for (int j=0; j < cols; j++)
      {
        inFile >> cell;
       
        if (cell == '*')
        {
          v[i][j] = true;
        }
        else if (cell == '.')
        {
          v[i][j] = false;
        }    
      }
    }    
  }

  inFile.close();  
}

void grid::printGrid()
{
  char cell;
 
  for (int i = 0; i < rows; i++)
  {
    for (int j = 0; j < cols; j++)
    {
      if (v[i][j] == true)
      {
         cell = '*';
      }
      else if (v[i][j] == false)
      {
         cell = '.';
      }  
     
      cout << cell;
    }
   
    cout << endl;
  }
}

int grid::getMaxBlob()
{
  return maxBlob;
}

bool grid::isEmpty()
{
  return v.empty();
}

void grid::findAllBlobs()
{
 
  int curSize = 0;
 
  for (int i=0; i < rows; i++)
  {  
    for (int j=0; j < cols; j++)
    {
      curSize = getBlobSize(i, j);
      if (curSize >= 2) cout << curSize << '\t';
      if (curSize > maxBlob) maxBlob = curSize;
    }
  }
  cout << endl;
}

int grid::getBlobSize(int curRow, int curCol)
{
  // I believe the run time error is caused somewhere in this function
  if (curRow > rows || curRow < 0 || curCol > cols || curCol < 0)
    return 0;
  else if (!v[curRow][curCol]) return 0;
  else
  {
    v[curRow][curCol] = 0;
   
    return 1 + getBlobSize(curRow - 1, curCol)
             + getBlobSize(curRow - 1, curCol + 1)
             + getBlobSize(curRow, curCol + 1)
             + getBlobSize(curRow + 1, curCol + 1)
             + getBlobSize(curRow + 1, curCol)
             + getBlobSize(curRow + 1, curCol - 1)
             + getBlobSize(curRow, curCol - 1)
             + getBlobSize(curRow - 1, curCol - 1);

  }
}

Here is the contents of the data file called "data.txt":

6 8
......*.
.**..*.*
.***..*.
..*.....
....*...
...**...

I've checked the function and can't find the problem. Any thoughts about why this error occurs and possible solutions would be greatly appreciated.

Thankyou.
0
Comment
Question by:Bonescraper
1 Comment
 
LVL 13

Accepted Solution

by:
SteH earned 60 total points
ID: 12141379
Most likely you need to return if
 if (curRow >= rows || curRow < 0 || curCol >= cols || curCol < 0)
Indices go from 0 to n-1 if array size is n.
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
AVI wait icons for CAnimateCtrl in Visual Studio 2008 MFC 1 119
How to split this in C++ 4 94
Unable to start eclipse ? 17 129
Least Squares Curve Fitting 4 60
Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

912 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now